Source-linked AI summary
A Lower Bound for the Distributed Lovász Local Lemma
Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, Jara Uitto
TL;DR
The paper addresses how many communication rounds randomized distributed algorithms need to construct satisfying assignments for the Lovász local lemma. It reduces LLL to sinkless orientation and uses a mutual speedup lemma, proving an Ω(log log n) lower bound even for constant dependency degree.
Problem
Before this work, the strongest known distributed LLL lower bound was Ω(log* n), while bounded-degree algorithms ran in O(log n) rounds.
Method
The proof reduces LLL algorithms to sinkless orientation in 3-regular graphs and applies a mutual speedup lemma relating sinkless orientation and sinkless colouring.
Results
Ω(log log n) communication rounds are required for randomized Monte Carlo distributed LLL algorithms that succeed with high probability, even when d=O(1).
Takeaways & Limitations
The lower bound strengthens the known distributed LLL barrier and also yields a lower bound for d-colouring d-regular high-girth graphs.
Takeaways & Limitations
The result is stated in the LOCAL model and uses high-girth graph instances in the sinkless-orientation lower-bound argument.
Abstract
from arXiv · showhide
We show that any randomised Monte Carlo distributed algorithm for the Lovász local lemma requires $Ω(\log \log n)$ communication rounds, assuming that it finds a correct assignment with high probability. Our result holds even in the special case of $d = O(1)$, where $d$ is the maximum degree of the dependency graph. By prior work, there are distributed algorithms for the Lovász local lemma with a running time of $O(\log n)$ rounds in bounded-degree graphs, and the best lower bound before our work was $Ω(\log^* n)$ rounds [Chung et al. 2014].
1 Introduction
The paper proves an Ω(log log n) communication-round lower bound for randomized distributed LLL algorithms, even when the dependency degree is constant. It derives this through reductions to sinkless orientation and a mutual speedup argument, improving the prior Ω(log* n) lower bound.
- Ω(log log n) rounds are necessary for randomized Monte Carlo distributed LLL algorithms with high-probability correctness, even when d=O(1).
- The result improves the previous distributed LLL lower bound from Ω(log* n), while prior bounded-degree algorithms required O(log n) rounds.
- The proof reduces distributed LLL to sinkless orientation in 3-regular graphs with asymptotically comparable running time.The reduction proceeds via a construction from LLL assignments to sinkless orientations.
- Sinkless orientation in 3-regular graphs requires Ω(log log n) rounds, establishing the lower bound used for LLL.
- A mutual speedup lemma alternates between sinkless colouring and sinkless orientation, reducing the running time by one round in one direction.Iterating this speedup would yield a zero-round algorithm, while the failure probability remains controlled for o(log log n) iterations.
- The lower bound also applies to d-colouring d-regular high-girth graphs because every proper d-colouring is a sinkless colouring.
2 Preliminaries
The paper defines sinkless orientation and colouring tasks, their relationship, and the LOCAL model’s round-based locality. It also formalizes distributed LLL assignments and the explicit finite-instance setting.
- 2.2 Model of Computation: The LOCAL model uses synchronous communication rounds, unrestricted message size and local computation, with each node eventually outputting its part of the solution.
- 2.3 Local Neighbourhoods: After t rounds, a node’s output depends only on its radius-t neighbourhood, and an edge’s output depends only on its corresponding edge neighbourhood.
- 2.4 Distributed Sinkless Orientation and Sinkless Colouring: The lower-bound framework studies sinkless tasks on d-regular graphs equipped with proper edge d-colourings.
- 2.4 Distributed Sinkless Orientation and Sinkless Colouring: A sinkless orientation directs every edge so each node has at least one outgoing edge, while a sinkless colouring forbids an edge whose endpoints both use that edge’s colour.
- 2.4 Distributed Sinkless Orientation and Sinkless Colouring: Sinkless orientation and sinkless colouring are closely related: orientation in t rounds gives colouring in t rounds, while colouring in t rounds gives orientation in t + 1 rounds.
- 2.5 Distributed Lovász Local Lemma: Distributed LLL assigns shared variable values consistently across adjacent events while avoiding every event, using explicit finite variable ranges and event specifications.
3 From LLL to Sinkless Orientation
The paper reduces distributed LLL to sinkless orientation by encoding orientations as shared LLL variables. For 3-regular graphs, it contracts colour-2 edges into virtual 4-regular nodes, simulates the LLL algorithm, and expands the result.
- 3 From LLL to Sinkless Orientation: An LLL algorithm satisfying pf(d) ≤ 1 yields a sinkless-orientation algorithm for 3-regular graphs of girth at least 5 with running time O(T).
- 3.1 Sinkless Orientation in 4-regular Graphs: The LLL variables represent edge orientations, while shared variables force adjacent event nodes to agree on every edge direction.
- 3.1 Sinkless Orientation in 4-regular Graphs: For 4-regular graphs, each node’s bad event is being a sink, occurring with probability 1/16 and depending on four others, so f(4) ≤ 16 suffices.
- 3.2 Sinkless Orientation in 3-regular Graphs: For 3-regular graphs, contracting every colour-2 edge creates a simple 4-regular virtual graph whose edges correspond uniquely to the original non-colour-2 edges.
- 3.2 Sinkless Orientation in 3-regular Graphs: After orienting the virtual graph, the algorithm orients contracted edges using leaders and relays, producing a sinkless orientation of the original graph.
- 3.2 Sinkless Orientation in 3-regular Graphs: The simulation incurs at most three original-graph rounds per virtual-graph round because adjacent virtual nodes’ leaders are at distance at most three.
4 The Mutual Speedup Lemma
The mutual speedup lemma converts sinkless colouring to sinkless orientation without increasing rounds, and converts orientation back to colouring while saving one round. On high-girth graphs, these transformations preserve correctness with controlled degradation of failure probabilities.
- Assumptions: The transformations assume 3-regular edge-coloured graphs whose girth exceeds 2t+1, making each relevant radius-(t+1) neighbourhood a tree.The tree structure supports the independence arguments used in the construction and analysis.
- 4.1 From Sinkless Colouring to Sinkless Orientation: The orientation construction gathers each node’s radius-t neighbourhood, computes candidate colours, evaluates neighbouring candidates, and orients edges according to one-sided candidacy.Edges with equal or absent candidacy are oriented arbitrarily with random tie-breaking.
- 4.1 From Sinkless Colouring to Sinkless Orientation: For a fixed neighbourhood, the candidate-colour set is empty with probability at most 3K, while nice edge neighbourhoods prevent the edge colour from being a candidate at both endpoints.Together with the local non-sink condition, these facts bound the orientation failure probability.
- 4.2 From Sinkless Orientation Back to Sinkless Colouring: A t-round sinkless orientation algorithm with sink probability at most ℓ yields a (t−1)-round sinkless colouring algorithm with forbidden-configuration probability below 4ℓ^1/4.This is the reverse direction of the mutual speedup lemma.
- Mutual Speedup: Applying the reverse transformation after the forward one gives a colouring speedup with forbidden-configuration probability below 4 · 6^1/4 · p^1/12.The composed bound follows from the two directions of the mutual speedup lemma.
5 Lower Bounds
The lower-bound argument iterates the colouring-to-colouring speedup on high-girth regular graphs until reaching zero rounds, where independent outputs contradict the required correctness probability. This establishes an Ω(log log n) lower bound for sinkless colouring, sinkless orientation, and constructive LLL algorithms.
- Graph Construction: The proof uses an infinite family of d-regular graphs with d-edge-colourings and girth Ω(log n), ensuring the high-girth speedup assumptions remain valid for the iteration.Bipartite double covers provide the corresponding d-regular bipartite graphs for the colouring corollary.
- Sinkless Colouring: Sinkless colouring on d-regular graphs requires Ω(log log n) rounds with high probability, obtained by iterating the reverse speedup on high-girth graph families.The proof assumes an o(log log n)-round algorithm, repeatedly reduces its running time, and reaches a zero-round contradiction.
- Sinkless Orientation: Sinkless orientation on d-regular graphs likewise has no high-probability Monte Carlo algorithm running in o(log log n) rounds.A sinkless colouring can be obtained from sinkless orientation without communication, transferring the lower bound.
- LLL Lower Bound: Any Monte Carlo distributed LLL algorithm satisfying pf(d) ≤ 1 and succeeding with high probability requires Ω(log log n) rounds, even when d=O(1).The result applies, for example, to the criteria ep(d+1) ≤ 1 and 4pd ≤ 1.