Fischer, Manuela ;
Ghaffari, Mohsen
Sublogarithmic Distributed Algorithms for Lovász Local Lemma, and the Complexity Hierarchy
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 nnode 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 vertexcoloring.
BibTeX  Entry
@InProceedings{fischer_et_al:LIPIcs:2017:7973,
author = {Manuela Fischer and Mohsen Ghaffari},
title = {{Sublogarithmic Distributed Algorithms for Lov{\'a}sz Local Lemma, and the Complexity Hierarchy}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {18:118:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770538},
ISSN = {18688969},
year = {2017},
volume = {91},
editor = {Andr{\'e}a W. Richa},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7973},
URN = {urn:nbn:de:0030drops79732},
doi = {10.4230/LIPIcs.DISC.2017.18},
annote = {Keywords: Distributed Graph Algorithms, the Lov'{a}sz Local Lemma (LLL), Locally Checkable Labeling problems (LCL), Defective Coloring, Frugal Coloring, List Ve}
}
2017
Keywords: 

Distributed Graph Algorithms, the Lov'{a}sz Local Lemma (LLL), Locally Checkable Labeling problems (LCL), Defective Coloring, Frugal Coloring, List Ve 
Seminar: 

31st International Symposium on Distributed Computing (DISC 2017)

Issue date: 

2017 
Date of publication: 

2017 