An Automatic Speedup Theorem for Distributed Problems

Recently, Brandt et al. [STOC'16] proved a lower bound for the distributed Lovász Local Lemma, which has been conjectured to be tight for sufficiently relaxed LLL criteria by Chang and Pettie [FOCS'17]. At the heart of their result lies a speedup technique that, for graphs of girth at least $2t+2$, transforms any $t$-round algorithm for one specific LLL problem into a $(t-1)$-round algorithm for the same problem. We substantially improve on this technique by showing that such a speedup exists for any locally checkable problem $Π$, with the difference that the problem $Π_1$ the inferred $(t-1)$-round algorithm solves is not (necessarily) the same problem as $Π$. Our speedup is automatic in the sense that there is a fixed procedure that transforms a description for $Π$ into a description for $Π_1$ and reversible in the sense that any $(t-1)$-round algorithm for $Π_1$ can be transformed into a $t$-round algorithm for $Π$. In particular, for any locally checkable problem $Π$ with exact deterministic time complexity $T(n, Δ) \leq t$ on graphs with $n$ nodes, maximum node degree $Δ$, and girth at least $2t+2$, there is a sequence of problems $Π_1, Π_2, \dots$ with time complexities $T(n, Δ)-1, T(n, Δ)-2, \dots$, that can be inferred from $Π$. As a first application of our generalized speedup, we solve a long-standing open problem of Naor and Stockmeyer [STOC'93]: we show that weak $2$-coloring in odd-degree graphs cannot be solved in $o(\log^* Δ)$ rounds, thereby providing a matching lower bound to their upper bound.