An Automatic Speedup Theorem for Distributed Problems
share
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, Δ) ≤ t on graphs with n nodes, maximum node degree Δ, and girth at least 2t+2, there is a sequence of problems Π_1, Π_2, ... with time complexities T(n, Δ)-1, T(n, Δ)-2, ..., 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(^* Δ) rounds, thereby providing a matching lower bound to their upper bound.
READ FULL TEXT