2026-07-21T21:09:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7973 2024-03-06T10:41:39Z ddc:004 open_access

Sublogarithmic Distributed Algorithms for Lovász Local Lemma, and the Complexity Hierarchy Fischer, Manuela Ghaffari, Mohsen Distributed Graph Algorithms the Lov'{a}sz Local Lemma (LLL) Locally Checkable Labeling problems (LCL) Defective Coloring Frugal Coloring List Ve 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Manuela Fischer and Mohsen Ghaffari 2017 Is Part Of LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2017.18 urn:nbn:de:0030-drops-79732 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.18 eng https://creativecommons.org/licenses/by/3.0/legalcode