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

doi:10.1145/2897518.2897570

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/konferenssijulkaisussa › Conference contribution › Scientific › vertaisarvioitu

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ä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	https://doi.org/10.1145/2897518.2897570
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

Pääsy asiakirjaan

10.1145/2897518.2897570

http://arxiv.org/abs/1511.00900

OpenUrl-saatavuus

Koko teksti

Muut tiedostot ja linkit

Link to publication in Scopus

Siteeraa tätä

@inproceedings{454bda56a2ad4cffb785abaa48115689,

title = "A lower bound for the distributed Lov{\'a}sz local lemma",

abstract = "We show that any randomised Monte Carlo distributed algorithm for the Lov{\'a}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{\'a}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].",

keywords = "Distributed complexity, Graph colouring, Locality, Lov{\'a}sz local lemma, Lower bounds, Sinkless orientations",

author = "Sebastian Brandt and Orr Fischer and Juho Hirvonen and Barbara Keller and Tuomo Lempi{\"a}inen and Joel Rybicki and Jukka Suomela and Jara Uitto",

year = "2016",

month = jun,

day = "19",

doi = "10.1145/2897518.2897570",

language = "English",

volume = "19-21-June-2016",

pages = "479--488",

booktitle = "STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing",

publisher = "ACM",

address = "United States",

note = "ACM Symposium on Theory of Computing, STOC ; Conference date: 19-06-2016 Through 21-06-2016",

}

Brandt, S, Fischer, O, Hirvonen, J, Keller, B, Lempiäinen, T, Rybicki, J, Suomela, J & Uitto, J 2016, A lower bound for the distributed Lovász local lemma. julkaisussa STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. Vuosikerta 19-21-June-2016, ACM, Sivut 479-488, ACM Symposium on Theory of Computing, Cambridge, Massachusetts, Yhdysvallat, 19/06/2016. https://doi.org/10.1145/2897518.2897570

TY - GEN

T1 - A lower bound for the distributed Lovász local lemma

AU - Brandt, Sebastian

AU - Fischer, Orr

AU - Hirvonen, Juho

AU - Keller, Barbara

AU - Lempiäinen, Tuomo

AU - Rybicki, Joel

AU - Suomela, Jukka

AU - Uitto, Jara

N1 - Conference code: 48

PY - 2016/6/19

Y1 - 2016/6/19

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

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

KW - Distributed complexity

KW - Graph colouring

KW - Locality

KW - Lovász local lemma

KW - Lower bounds

KW - Sinkless orientations

UR - http://www.scopus.com/inward/record.url?scp=84979249230&partnerID=8YFLogxK

U2 - 10.1145/2897518.2897570

DO - 10.1145/2897518.2897570

M3 - Conference contribution

AN - SCOPUS:84979249230

VL - 19-21-June-2016

SP - 479

EP - 488

BT - STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing

PB - ACM

T2 - ACM Symposium on Theory of Computing

Y2 - 19 June 2016 through 21 June 2016

ER -

A lower bound for the distributed Lovász local lemma

Abstrakti

Conference

Pääsy asiakirjaan

OpenUrl-saatavuus

Muut tiedostot ja linkit

Sormenjälki

Siteeraa tätä