The Moser-Tardos Algorithm

Some problems look hopelessly tangled: you have a large set of bad events you want to avoid, and each variable you choose affects several of them. The naive hope — pick everything independently at random and pray — fails if any single event is too likely.

In 1975, Lovász and Erdős proved the Lovász Local Lemma (LLL): if each bad event has probability at most $p$, each event shares variables with at most $d$ others, and $ep(d+1) \leq 1$, then there exists an assignment avoiding all bad events. Beautiful — but for 35 years the proof was purely existential. It told you a good assignment was out there somewhere, but gave no recipe for finding it.

In 2009, Robin Moser and Gábor Tardos closed that gap. Their algorithm is breathtakingly simple: pick all variables uniformly at random; while any bad event is violated, resample the variables of one violated event. That's it. Under the LLL condition the process terminates in expected polynomial time and hands you a valid assignment.

The Moser-Tardos result turned a celebrated existence theorem into a practical tool, placing it squarely in the algorithmic toolkit for randomized algorithms and constraint satisfaction.

Below is a small instance of the LLL setting: ten binary variables $x_1, \dots, x_{10}$ and eight constraints, each forbidding one specific pattern on three of those variables. Each constraint touches at most four other constraints — well within the LLL bound.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<div id="var-row" class="var-row" aria-label="{{vars_label}}"></div>
<div id="constraints-area" class="constraints-area" aria-label="{{constraints_label}}"></div>
<div class="status-bar" id="status">{{status_init}}</div>
<div class="log-box" id="log" aria-label="{{log_label}}"></div>
<div class="btns">
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.5; }
.var-row { display: flex; flex-wrap: wrap; gap: 6px; margin-bottom: .6rem; }
.var-box { width: 44px; height: 44px; display: flex; align-items: center; justify-content: center;
           font: 700 15px ui-monospace, monospace; border-radius: 8px; border: 1.5px solid #adb1b8;
           background: #e0e7ef; color: #1d3557; transition: background .2s, border-color .2s; }
.var-box.val-1 { background: #d0f0d8; border-color: #2a9d4a; color: #1a6632; }
.var-box.val-0 { background: #f5e0e3; border-color: #c92f3c; color: #7a1a1f; }
.var-box.resampled { outline: 3px solid #f4a261; outline-offset: 2px; }
.constraints-area { display: flex; flex-wrap: wrap; gap: 6px; margin-bottom: .5rem; }
.c-chip { font-size: .78rem; padding: 4px 8px; border-radius: 6px; border: 1.5px solid #cdd9e3;
          background: #f0f4f8; color: #333; transition: background .2s, border-color .2s; }
.c-chip.violated { background: #fde9ea; border-color: #c92f3c; color: #7a1a1f; font-weight: 700; }
.c-chip.satisfied { background: #d5f2e0; border-color: #2a9d4a; color: #1a6632; }
.status-bar { font-size: .97rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; }
.status-bar.ok { color: #0a7d33; }
.status-bar.bad { color: #c92f3c; }
.status-bar.running { color: #e76f00; }
.log-box { font-size: .78rem; font-family: ui-monospace, monospace; color: #444;
           max-height: 90px; overflow-y: auto; border: 1px solid #cdd9e3; border-radius: 6px;
           padding: 4px 8px; margin-bottom: .5rem; background: #fafafa; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .42rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

// Code not found

Press Run Moser-Tardos to watch the algorithm: it initializes all variables randomly, then repeatedly finds a violated constraint and resamples only its variables. The log shows each resampling step. Because the dependency graph is sparse, the LLL guarantees termination — and in practice you see it finish in just a few rounds.

How fast is the algorithm, and why does it terminate at all?

• Each resampling step is cheap: find a violated constraint, draw fresh independent bits for its variables, check all constraints that share those variables. No global search, no backtracking.
• The termination argument is elegant. Moser and Tardos defined a potential function based on the entropy of a hypothetical "witness tree": a record of which constraint was resampled at each step. They showed that as long as the LLL condition $ep(d+1) \leq 1$ holds, the witness tree cannot grow unboundedly — thus the algorithm must stop.
• Expected runtime: under the symmetric LLL condition, the expected number of resamplings is at most $\frac{n \cdot p}{1 - ep(d+1)}$, essentially linear in the number of variables once the slack is bounded away from zero.
• Tightness: the condition $ep(d+1) \leq 1$ is essentially tight. Push past it and you can construct instances where no good assignment exists.

The Moser-Tardos paper won the STOC 2009 Best Paper Award and was published in the Journal of the ACM in 2010. Its entropy-based proof technique has since inspired constructive versions of many other probabilistic arguments, including graph coloring and scheduling results.

"Avoid all these bad events while each depends only locally on the others" is a surprisingly common shape:

• $k$-SAT: a random assignment to a $k$-CNF formula with at most $2^k / (ek)$ occurrences per variable satisfies all clauses. Moser-Tardos makes this constructive.
• Graph coloring: every graph of maximum degree $\Delta$ has a proper $(\Delta+1)$-coloring. Resampling gives a fast randomized algorithm to find one.
• Packet scheduling: in optical networks, frames must be scheduled so no two conflict in the same time slot. Sparse conflict structure is exactly the LLL regime.
• Coding theory: constructing error-correcting codes with large minimum distance often reduces to satisfying many local parity constraints simultaneously.
• Combinatorial geometry: existence results on discrepancy, coloring of hypergraphs, and Ramsey-type problems all benefit from constructive LLL.

The broader lesson is that whenever a probabilistic argument invokes independence or near-independence to show something exists, the Moser-Tardos framework is a candidate for turning that proof into an algorithm.

The Moser-Tardos algorithm is a masterclass in converting a probabilistic existence proof into a practical procedure. The insight is almost paradoxical: instead of searching for a good assignment cleverly, just keep fixing whatever is broken — and the entropy of the process guarantees you cannot fix things forever without finding a valid state.

It is a reminder that the boundary between "this exists" and "we can find it" is not always where intuition places it. Sometimes the simplest imaginable loop, run long enough under the right sparsity condition, is all you need — and the Lovász Local Lemma tells you exactly when that is enough.