Title: 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.