arXiv (Cornell University) · 2017 · 46 citations · 0 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationComputational ComplexityDistributed AlgorithmsDistributed ComputingGraph AlgorithmsRandomized ComplexityTime ComplexityComputational Complexity Of Graph AlgorithmsLovász Local LemmaLower BoundsLower Bounds For Randomized AlgorithmsNode DegreeRandomized Complexity TheoryRandomized Graph Algorithms
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