Abstrakti
We show that any randomised Monte Carlo distributed algorithm for the Lovász local lemma requires Ω(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(logn) rounds in bounded-degree graphs, and the best lower bound before our work was Ω(log∗ n) rounds [Chung et al. 2014].
Alkuperäiskieli | Englanti |
---|---|
Otsikko | STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing |
Kustantaja | ACM |
Sivut | 479-488 |
Sivumäärä | 10 |
Vuosikerta | 19-21-June-2016 |
ISBN (elektroninen) | 9781450341325 |
DOI - pysyväislinkit | |
Tila | Julkaistu - 19 kesäk. 2016 |
OKM-julkaisutyyppi | A4 Artikkeli konferenssijulkaisuussa |
Tapahtuma | ACM Symposium on Theory of Computing - Cambridge, Yhdysvallat Kesto: 19 kesäk. 2016 → 21 kesäk. 2016 Konferenssinumero: 48 |
Conference
Conference | ACM Symposium on Theory of Computing |
---|---|
Lyhennettä | STOC |
Maa/Alue | Yhdysvallat |
Kaupunki | Cambridge |
Ajanjakso | 19/06/2016 → 21/06/2016 |