Abstract
We consider the task of designing Local Computation Algorithms (LCA) for applications of the Lovász Local Lemma (LLL). LCA is a class of sublinear algorithms that have received significant attention for their ability to provide local views of global solutions. While the ground-breaking algorithm of Moser and Tardos (MT) made the LLL fully constructive, previous LCAs required significantly stronger conditions than the standard LLL threshold. This paper answers an open question by showing that the Moser-Tardos algorithm can indeed be used to design LCAs under standard LLL conditions. Our techniques yield LCAs that are efficient even beyond the standard LLL setting, providing sublinear and often polylogarithmic query times.
Introduction
The Lovász Local Lemma (LLL) is a cornerstone of probabilistic combinatorics, providing a sufficient condition for a collection of "bad events" to have a non-empty intersection. Essentially, it proves that a "perfect object"—such as a valid graph coloring or a satisfying assignment for a formula—exists, provided that the events are not too likely and not too interdependent.
In 2010, Moser and Tardos revolutionized the field by providing a simple "Resample" algorithm that actually finds these objects. However, in the era of massive datasets, computing an entire global solution is often impractical. We may only need to know a small part of the solution, such as the color of a single vertex in a graph with billions of nodes. This is the domain of Local Computation Algorithms (LCA). The challenge addressed in this paper is that previous LCAs for LLL-related problems required much stricter conditions than the standard LLL. This work demonstrates that the simple Moser-Tardos approach can be adapted into an LCA that works right up to the standard LLL threshold.
The Depth-First Moser-Tardos Algorithm
The authors propose a "meta-algorithm" based on a variation of the Moser-Tardos approach called Depth-First MT. To answer a query for a specific variable $x$, the algorithm follows a localized execution path:
- Neighborhood Definition: The algorithm identifies all constraints within a distance $r$ of the variable in the "dependency graph" (where edges represent shared variables between constraints).
- Local Execution: It runs the Moser-Tardos resampling algorithm only on this local sub-problem for a fixed number of steps $t$.
- Consistency: To ensure that answers to multiple queries are consistent with a single global solution, the algorithm maintains a local memory of previously assigned values and uses a specific strategy for choosing which bad events to fix.
The Radius of Influence
The mathematical foundation of this approach relies on Witness Trees. The authors prove that the "badness" of a conflict propagates like a wave. By clearing a sufficiently large radius $r$ around a query, the algorithm creates a buffer zone. The probability that a conflict from outside this zone propagates to the center and forces $x$ to change is exponentially small in $r$ (specifically $e^{-\Omega(r)}$). This "Radius of Influence" allows the algorithm to be "strongly local," meaning the time and space required per query are only polylogarithmic in the size of the total problem.
Key Results and Applications
The main result, Theorem 3.1, proves the existence of an LCA that can handle $n^\alpha$ queries, each in $n^\beta$ time, with a failure probability of only $n^{-\gamma}$. Unlike previous work that required conditions like $d(k+1) < 2^{k/16}$ for $k$-SAT, this work operates under the standard LLL limit (e.g., $d(k+1) \leq 2^{k+1}/e$), provided there is a small constant factor of "slack" ($\epsilon > 0$).
The authors demonstrate the power of this algorithm by applying it to three classic problem classes:
- $k$-SAT: Finding satisfying assignments for Boolean formulas where each variable appears in a limited number of clauses.
- Graph Coloring: Finding valid vertex colorings for graphs with specific maximum degrees and neighborhood structures.
- Hypergraph Coloring: 2-coloring non-uniform hypergraphs where edges have varying sizes.
Discussion and Limitations
A key insight of this work is Strategy Independence. The Moser-Tardos algorithm converges regardless of the order in which violated constraints are fixed. By choosing a "query-centric" strategy that prioritizes fixing events near the user's query, the authors achieve high efficiency.
However, some limitations remain. The algorithm requires the LLL condition to hold with some $\epsilon$-slack; the behavior exactly at the critical threshold ($\epsilon = 0$) is still unknown. Additionally, while the time per query is sublinear, the algorithm must remember assigned values to remain consistent across multiple queries, which could create a memory bottleneck for an extremely high number of queries. Future research may extend these techniques to more abstract "commutative" algorithmic settings beyond the variable-based model.
Summary updated