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 $\mathsf{LOCAL}$ distributed algorithms. In a recent enlightening revelation, Chang and Pettie [arXiv 1704.06297] 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 Lovász 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. 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.