Sublogarithmic Distributed Algorithms for Lov\\'asz Local lemma, and the\n Complexity Hierarchy

Manuela Fischer, Mohsen Ghaffari

arXiv (Cornell University) · 2017 · 46 citations · 0 references

DOIFull text

Open access

Concepts

Abstract

Locally Checkable Labeling (LCL) problems include essentially all the classic\nproblems of $\\mathsf{LOCAL}$ distributed algorithms. In a recent enlightening\nrevelation, Chang and Pettie [arXiv 1704.06297] showed that any LCL (on bounded\ndegree graphs) that has an $o(\\log n)$-round randomized algorithm can be solved\nin $T_{LLL}(n)$ rounds, which is the randomized complexity of solving (a\nrelaxed variant of) the Lov\\'asz Local Lemma (LLL) on bounded degree $n$-node\ngraphs. Currently, the best known upper bound on $T_{LLL}(n)$ is $O(\\log n)$,\nby Chung, Pettie, and Su [PODC'14], while the best known lower bound is\n$\\Omega(\\log\\log n)$, by Brandt et al. [STOC'16]. Chang and Pettie conjectured\nthat there should be an $O(\\log\\log n)$-round algorithm.\n Making the first step of progress towards this conjecture, and providing a\nsignificant improvement on the algorithm of Chung et al. [PODC'14], we prove\nthat $T_{LLL}(n)= 2^{O(\\sqrt{\\log\\log n})}$. Thus, any $o(\\log n)$-round\nrandomized distributed algorithm for any LCL problem on bounded degree graphs\ncan be automatically sped up to run in $2^{O(\\sqrt{\\log\\log n})}$ rounds.\n Using this improvement and a number of other ideas, we also improve the\ncomplexity of a number of graph coloring problems (in arbitrary degree graphs)\nfrom the $O(\\log n)$-round results of Chung, Pettie and Su [PODC'14] to\n$2^{O(\\sqrt{\\log\\log n})}$. These problems include defective coloring, frugal\ncoloring, and list vertex-coloring.\n