A lower bound for the distributed Lovász local lemma

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussavertaisarvioitu

Tutkijat

Organisaatiot

  • Swiss Federal Institute of Technology Zurich
  • Tel Aviv University
  • Bitsplitters GmbH

Kuvaus

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].

Yksityiskohdat

AlkuperäiskieliEnglanti
OtsikkoSTOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing
TilaJulkaistu - 19 kesäkuuta 2016
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaACM Symposium on Theory of Computing - Cambridge, Yhdysvallat
Kesto: 19 kesäkuuta 201621 kesäkuuta 2016
Konferenssinumero: 48

Conference

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

ID: 5565389