Source-linked AI summary
An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie
TL;DR
The paper studies why randomized distributed algorithms can outperform deterministic ones in the LOCAL model and establishes structural connections between their complexities. It proves randomized and deterministic bounds for Δ-coloring trees, derives deterministic gaps from lower bounds, and shows how graph shattering underlies randomized complexity.
Problem
The paper investigates the value of random bits in distributed symmetry breaking, where deterministic processes can face impossibility or substantially higher complexity.
Method
The paper combines lower-bound reductions with graph-shattering arguments that fix part of the output and reduce the remaining problem to small components solvable deterministically.
Results
Δ-coloring trees takes Ω(log_Δ log n) randomized time and Ω(log_Δ n) deterministic time, while deterministic lower bounds also transfer to randomized lower bounds through the paper’s complexity connections.
Takeaways & Limitations
Graph shattering is inherent to optimal randomized LOCAL algorithms, and deterministic lower bounds can impose randomized lower bounds at logarithmically smaller instance scales.
Takeaways & Limitations
The fast randomized Δ-coloring result is established for Δ≥55, and the analyzed approach requires sufficiently large degree for its probabilistic bounds to work effectively.
Abstract
from arXiv · showhide
Over the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge-coloring. For most problems the best randomized algorithm is at least exponentially faster than the best deterministic algorithm. In this paper we prove that these exponential gaps are necessary and establish connections between the deterministic and randomized complexities in the LOCAL model. Each result has a very compelling take-away message: 1. Fast $Δ$-coloring of trees requires random bits: Building on the recent lower bounds of Brandt et al., we prove that the randomized complexity of $Δ$-coloring a tree with maximum degree $Δ\ge 55$ is $Θ(\log_Δ\log n)$, whereas its deterministic complexity is $Θ(\log_Δn)$ for any $Δ\ge 3$. This also establishes a large separation between the deterministic complexity of $Δ$-coloring and $(Δ+1)$-coloring trees. 2. Randomized lower bounds imply deterministic lower bounds: We prove that any deterministic algorithm for a natural class of problems that runs in $O(1)+o(\log_Δn)$ rounds can be transformed to run in $O(\log^*n-\log^*Δ+1)$ rounds. If the transformed algorithm violates a lower bound (even allowing randomization), then one can conclude that the problem requires $Ω(\log_Δn)$ time deterministically. 3. Deterministic lower bounds imply randomized lower bounds: We prove that the randomized complexity of any natural problem on instances of size $n$ is at least its deterministic complexity on instances of size $\sqrt{\log n}$. This shows that a deterministic $Ω(\log_Δn)$ lower bound for any problem implies a randomized $Ω(\log_Δ\log n)$ lower bound. It also illustrates that the graph shattering technique is absolutely essential to the LOCAL model.
1 Introduction
The paper studies when random bits improve distributed symmetry breaking in the LOCAL model, distinguishing RandLOCAL from DetLOCAL. It proves exponential separations for specific problems and general connections between randomized and deterministic complexities for locally checkable labeling problems.
- LOCAL models: RandLOCAL allows local random bits and bounded global failure probability, whereas DetLOCAL uses unique Θ(log n)-bit IDs and deterministic algorithms.Both models count only communication rounds; local computation is free and messages are unbounded.
- Randomized speedups: Graph shattering fixes part of the output randomly, leaves poly(log n)-size components, and applies deterministic algorithms to those components in parallel.This approach explains why randomized algorithms can improve dependence on Δ while retaining similar dependence on n.
- Δ-coloring separation: RandLOCAL lower bounds of Ω(log_Δ log n) and DetLOCAL lower bounds of Ω(log_Δ n) hold for Δ-coloring degree-Δ graphs and trees.For trees, the deterministic lower bound follows from hard high-girth graphs and indistinguishability; the randomized lower bound incorporates error probabilities.
- Δ-coloring separation: For Δ≥55, Δ-coloring trees has a randomized upper bound O(log_Δ log n + log* n), while for Δ≥3 its deterministic upper bound is O(log_Δ n + log* n).The randomized upper bound matches the randomized lower bound up to the log* n term.
- Randomized lower bounds: For any LCL, randomized complexity on size-n instances is at least deterministic complexity on size-√log n instances.Thus deterministic lower bounds transfer to randomized lower bounds, and improving several randomized algorithms requires improving corresponding deterministic algorithms.
2 Preliminaries
The preliminaries define LOCAL graph notation, LCL problems, and the principal symmetry-breaking tasks used throughout. They also introduce Linial’s deterministic recoloring tools.
- Locally Checkable Labeling: LCL problems have solutions verifiable within a fixed-radius neighborhood using a finite labeling scheme.For each vertex, the labeled radius-r neighborhood must belong to an allowed collection; invalid instances admit no such labeling.
- Symmetry-breaking problems: MIS selects vertices so that membership is equivalent to having no neighboring selected vertex.
- Symmetry-breaking problems: k-Coloring assigns one of k colors to every vertex, with adjacent vertices receiving different colors.
- Sinkless problems: ∆-Sinkless Coloring forbids an edge whose endpoints and edge label all share one color, while ∆-Sinkless Orientation requires every vertex to have an outgoing edge.
- Linial’s coloring: Linial’s recoloring algorithm converts a k-colored graph into a 5∆^2 log k-colored graph in one deterministic round.
- Linial’s coloring: A universal constant β enables deterministic β·∆^2-coloring in O(log∗n − log∗∆ + 1) time.
3 The Necessity of Graph Shattering
The paper formalizes how deterministic and randomized LOCAL complexities constrain each other. Its derandomization argument converts a randomized algorithm into a deterministic one by fixing a globally good mapping from identifiers to random strings.
- Randomized-to-deterministic connections: Theorem 3 states that randomized complexity for any LCL is bounded below by deterministic complexity on smaller instances.The theorem defines DetP(n, ∆) and RandP(n, ∆) under global error probability 1/n.
- Derandomization: A randomized algorithm can be derandomized by assigning each identifier a fixed random-bit string through a function φ.The deterministic simulation runs the randomized algorithm with φ(ID(v)) replacing locally generated randomness.
- Derandomization: A lexicographically first good function φ⋆ exists because the failure probability and union bound guarantee at least one function succeeds on every relevant instance.
- Derandomization: The resulting deterministic algorithm computes φ⋆ and then executes the fixed-randomness simulation without errors on the targeted graph family.
- Scope: The framework extends to parameters depending on degree, local sparsity, arboricity, degeneracy, or neighborhood growth.
- Consequences: Algorithms running in 2^O(log∗n) randomized time can be derandomized with no asymptotic penalty.
4 Lower bounds for ∆-coloring ∆-regular Trees
The paper proves an exponential randomized–deterministic gap for ∆-coloring degree-∆ graphs and trees. Randomized lower bounds arise through reductions between sinkless coloring and sinkless orientation, while deterministic lower bounds require handling identifiers separately.
- Main lower bounds: ∆-coloring requires Ω(log_∆ log n) randomized time and Ω(log_∆ n) deterministic time on suitable graphs and ∆-regular trees.The lower-bound graphs have girth Ω(log_∆ n), allowing the graph bounds to transfer to trees by indistinguishability.
- Reduction framework: Sinkless-coloring algorithms can be transformed into sinkless-orientation algorithms, and vice versa, with controlled changes in rounds and local failure probabilities.The reductions apply on ∆-regular graphs with proper edge colorings and sufficiently large girth.
- Randomized lower bound: Any randomized ∆-coloring algorithm with error probability p requires at least min{ε log^3(∆+1) ln(1/p), ε log_∆ n} rounds.
- Randomized lower bound: For global error probability 1/poly(n), randomized ∆-coloring takes Ω(log_∆ log n) time.
- Deterministic lower bound: The randomized lower bound does not immediately extend to DetLOCAL because deterministic vertices initially possess unique O(log n)-bit identifiers.
- Deterministic lower bound: The deterministic lower bound is obtained by using locally generated random identifiers and recoloring neighborhoods so that a deterministic algorithm behaves as though identifiers were unique.
5 Gaps in Deterministic Time Complexity
The paper develops a speedup technique for deterministic LCL algorithms on hereditary graph classes, yielding gaps and dichotomies in possible deterministic complexities. For constant degree, complexities are forced toward very fast or substantially slower regimes.
- Speedup theorem: Theorem 6 transforms an algorithm running in f(∆)+o(log_∆ n) time into one running in O((1+f(∆))(log∗n−log∗∆+1)) time.
- Speedup construction: The speedup shortens identifiers within neighborhoods, simulates the original algorithm on the shortened identifiers, and preserves legality through heredity of the graph class.
- Application to ∆-coloring: Combining the speedup with randomized lower bounds yields deterministic Ω(log_∆ n) lower bounds for ∆-coloring in the relevant parameter range.
- Complexity gaps: For constant ∆ on hereditary graph classes, every LCL problem has deterministic complexity either Ω(log n) or O(log∗n).
- Degree-two case: When ∆=2, every LCL problem on a hereditary graph class has deterministic complexity either Ω(n) or O(log∗n).
- Generalized speedup: The transformed algorithm’s total complexity is O(log^k ∆(log∗n−log∗∆+1)) when the original runtime is O(log^k ∆+log^(k+1) n).
6 Algorithms for ∆-coloring Trees
This section presents randomized and deterministic algorithms for Δ-coloring trees, including a two-phase randomized method whose runtime is O(log_Δ log n + log*n) for Δ≥55. The analysis uses random partial coloring, filtering, and deterministic completion on small residual components.
- Ω(log_Δn) deterministic and Ω(log_Δlog n) randomized lower bounds for Δ-coloring trees have matching upper bounds up to an additive log*n term.
- For Δ≥3, deterministic Δ-coloring of trees takes O(log_Δn + log*n) time.
- For sufficiently large Δ, randomized Δ-coloring runs in O(log_Δlog n + log*n) time, while the earlier proof did not provide a convenient explicit threshold.
- Algorithm structure: The randomized algorithm uses O(log*Δ) rounds of partial coloring followed by deterministic coloring of remaining vertices with reserved colors.
- Algorithm structure: ColorBidding selects random color subsets, and Filtering removes vertices that could violate the large-palette or small-degree properties.
- Analysis and runtime: The residual bad-vertex components are bounded by O(log n) with high probability, enabling deterministic completion and yielding total runtime O(log_Δlog n + log*n).
- The simplified algorithm establishes a randomized Δ-coloring algorithm for every Δ≥55.
A Proofs of Claims 1, 2, and 3
These proofs maintain large palettes and controlled residual degrees through randomized coloring and filtering. Chernoff bounds then show that the relevant neighborhood and palette conditions hold with high probability.
- The filtering rules preserve the Large Palette Property and Small Degree Property after each round.
- In the first round, tree structure makes neighbors’ coloring events independent, allowing concentration bounds on the number of colored neighbors.
- Random color selection and repeated-color filtering ensure that many available colors remain while vertices with insufficient slack are marked bad.
- For each round, a vertex remains uncolored with probability bounded by an exponential term determined by the palette-selection parameter c_i.
- Applying concentration bounds across neighboring vertices yields the required bounds on the next-round residual degree with high probability.
B Proof of Claim 4
The proof of Claim 4 bounds the probability that a vertex remains in the exceptional set by analyzing how many neighbors receive each color. For Δ≥55, the resulting probability is sufficiently small for the component-size argument.
- A vertex belongs to the exceptional set only if, across the relevant steps, at most one neighbor receives each considered color.
- The probability that a neighbor receives a color is analyzed using an auxiliary random variable and the condition that competing neighbors have larger values.
- For Δ≥55, numerical evaluation gives a sufficiently small conditional probability that a vertex belongs to the exceptional set, with the bound improving monotonically as the relevant index increases.