the Moser-Tardos algorithm
/ MOH-zer TAR-dosh /
The Moser-Tardos algorithm is the constructive, algorithmic version of the Lovasz Local Lemma. The classical LLL proves that a configuration avoiding all bad events exists, but its proof is an existence argument that gives no efficient way to actually produce one. For decades this was a genuine gap: one knew a good object was there but could not find it in polynomial time. In 2009 Robin Moser, and then Moser and Gabor Tardos in full generality, gave a stunningly simple randomised algorithm that finds a good configuration efficiently under essentially the same condition as the LLL, with a beautiful entropy-compression proof of why it terminates fast.
The setting is the variable version of the LLL: bad events B_i are determined by an underlying set of mutually independent random variables, and each B_i depends on a small subset of them (its scope). The algorithm is almost embarrassingly direct. Sample all variables from their distributions. Then, while some bad event B_i currently holds, pick such a violated event and resample (only) the variables in its scope, drawing them afresh from their distributions; repeat. Moser and Tardos proved that if the LLL condition holds (the asymmetric criterion P(B_i) <= x_i times the product of (1 - x_j) over dependency neighbours), this loop terminates after an expected number of resamplings at most sum of x_i/(1 - x_i) — polynomial in the number of events — and ends, necessarily, at a configuration with no bad event. The whole correctness argument fits on a page.
Why it terminates is the deep part, and the proof itself is a flagship of the entropy compression method. One records an execution log (the witness tree of which events were resampled), and shows that a long run would let you compress the sequence of random bits consumed below its own length, which is impossible — randomness cannot be compressed. This converts the algorithm's running time into an information-theoretic counting argument. The practical payoff is that nearly every classical LLL existence result (hypergraph colourings, k-SAT, acyclic edge colourings, and more) becomes a polynomial-time randomised algorithm with essentially no loss in the parameters. The honest caveat is the variable-model requirement: the cleanest Moser-Tardos theorem needs the bad events to be defined by independent variables with local scopes; extending the algorithmic LLL to the most general abstract or lopsided settings (the Moser-Tardos distribution, entropy compression beyond the variable model) required substantial further work and does not come for free.
k-SAT, made constructive: start with a uniformly random truth assignment. While some clause is unsatisfied, pick one and re-flip fresh random coins for its k variables; repeat. If e * 2^(-k)(d+1) <= 1 (the LLL bound, with d the clause-overlap degree), Moser-Tardos guarantees this halts after O(m) expected resamplings on a formula with m clauses, returning an actual satisfying assignment — not merely a proof one exists.
Resample the variables of any violated event until none is violated — it provably halts fast under the LLL condition.
The clean Moser-Tardos result needs the variable model (events defined by independent variables on local scopes); extending the algorithmic and lopsided LLL beyond this is genuine extra work, not automatic.