A lower bound for the distributed Lovász local lemma

Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, Jara Uitto

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

96 Sitaatiot (Scopus)

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äiskieliEnglanti
OtsikkoSTOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing
KustantajaACM
Sivut479-488
Sivumäärä10
Vuosikerta19-21-June-2016
ISBN (elektroninen)9781450341325
DOI - pysyväislinkit
TilaJulkaistu - 19 kesäk. 2016
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaACM Symposium on Theory of Computing - Cambridge, Yhdysvallat
Kesto: 19 kesäk. 201621 kesäk. 2016
Konferenssinumero: 48

Conference

ConferenceACM Symposium on Theory of Computing
LyhennettäSTOC
Maa/AlueYhdysvallat
KaupunkiCambridge
Ajanjakso19/06/201621/06/2016

Sormenjälki

Sukella tutkimusaiheisiin 'A lower bound for the distributed Lovász local lemma'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä