Sublogarithmic distributed algorithms for lovász local lemma, and the complexity hierarchy
Open access
Datum
2017Typ
- Conference Paper
Abstract
Locally Checkable Labeling (LCL) problems include essentially all the classic problems of LOCAL distributed algorithms. In a recent enlightening revelation, Chang and Pettie [FOCS'17] showed that any LCL (on bounded degree graphs) that has an o(log n)-round randomized algorithm can be solved in T_(LLL)(n) rounds, which is the randomized complexity of solving (a relaxed variant of) the Lovasz Local Lemma (LLL) on bounded degree n-node graphs. Currently, the best known upper bound on T_(LLL)(n) is O(log n), by Chung, Pettie, and Su [PODC'14], while the best known lower bound is Omega(log log n), by Brandt et al. [STOC'16]. Chang and Pettie conjectured that there should be an O(log log n)-round algorithm (on bounded degree graphs). Making the first step of progress towards this conjecture, and providing a significant improvement on the algorithm of Chung et al. [PODC'14], we prove that T_(LLL)(n)= 2^O(sqrt(log log n)). Thus, any o(log n)-round randomized distributed algorithm for any LCL problem on bounded degree graphs can be automatically sped up to run in 2^O(sqrt(log log n)) rounds. Using this improvement and a number of other ideas, we also improve the complexity of a number of graph coloring problems (in arbitrary degree graphs) from the O(log n)-round results of Chung, Pettie and Su [PODC'14] to 2^O(sqrt(log log n)). These problems include defective coloring, frugal coloring, and list vertex-coloring. Mehr anzeigen
Persistenter Link
https://doi.org/10.3929/ethz-b-000205785Publikationsstatus
publishedExterne Links
Herausgeber(in)
Buchtitel
31st International Symposium on Distributed Computing (DISC 2017)Zeitschrift / Serie
Leibniz International Proceedings in Informatics (LIPIcs)Band
Seiten / Artikelnummer
Verlag
Schloss Dagstuhl - Leibniz-Zentrum für InformatikKonferenz
Thema
Distributed Graph Algorithms; the Lovász Local Lemma (LLL); Locally Checkable Labeling problems (LCL); Defective Coloring; Frugal Coloring; List Vertex-ColoringOrganisationseinheit
00002 - ETH Zürich09587 - Ghaffari, Mohsen (ehemalig) / Ghaffari, Mohsen (former)