Name
Abstract | ||
|---|---|---|
We show that any randomised Monte Carlo distributed algorithm for the Lovász local lemma requires Omega(log log n) communication rounds, assuming that it finds a correct assignment with high probability. Our result holds even in the special case of d = O(1), where d is the maximum degree of the dependency graph. By prior work, there are distributed algorithms for the Lovász local lemma with a running time of O(log n) rounds in bounded-degree graphs, and the best lower bound before our work was Omega(log* n) rounds [Chung et al. 2014]. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1145/2897518.2897570 | STOC |
Keywords | DocType | Volume |
Lovasz local lemma,distributed complexity,lower bounds,locality,graph colouring,sinkless orientations | Conference | abs/1511.00900 |
ISSN | Citations | PageRank |
0737-8017 | 22 | 0.78 |
References | Authors | |
26 | 8 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sebastian C. Brandt | 1 | 274 | 27.02 |
| Orr Fischer | 2 | 30 | 4.97 |
| Juho Hirvonen | 3 | 106 | 11.81 |
| Barbara Keller | 4 | 30 | 4.12 |
| Tuomo Lempiäinen | 5 | 55 | 4.35 |
| Joel Rybicki | 6 | 78 | 9.69 |
| Jukka Suomela | 7 | 600 | 46.99 |
| Jara Uitto | 8 | 107 | 17.08 |