47 citations · 107 across the 20 of their papers we have counts for
4 papers · 1 filter
Non-Local Probes Do Not Help with Graph Problems
Mika Göös, Juho Hirvonen, Reut Levi +2
This work bridges the gap between distributed and centralised models of computing in the context of sublinear-time graph algorithms. A priori, typical centralised models of computi…
A Lower Bound for the Distributed Lovász Local Lemma
Sebastian Brandt, Orr Fischer, Juho Hirvonen +5
We show that any randomised Monte Carlo distributed algorithm for the Lovász local lemma requires communication rounds, assuming that it finds a correct assignment…
Node Labels in Local Decision
Pierre Fraigniaud, Juho Hirvonen, Jukka Suomela
The role of unique node identifiers in network computing is well understood as far as symmetry breaking is concerned. However, the unique identifiers also leak information about th…
Locally Optimal Load Balancing
Laurent Feuilloley, Juho Hirvonen, Jukka Suomela
This work studies distributed algorithms for locally optimal load-balancing: We are given a graph of maximum degree , and each node has up to units of load. The task is to d…