Papers › An Automatic Speedup Theorem for Distributed Problems
An Automatic Speedup Theorem for Distributed Problems
Sebastian Brandt
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Recently, Brandt et al. [STOC'16] proved a lower bound for the distributed Lov\'asz 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 Π₁ 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 Π₁ and reversible in the sense that any (t-1)-round algorithm for Π₁ 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 Π₁, Π₂, … 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(log^* Δ) rounds, thereby providing a matching lower bound to their upper bound.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections