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 article in proceedingsScientificvertaisarvioitu

116 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 konferenssijulkaisussa
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ä