Introduction

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 pp, each event shares variables with at most dd others, and ep(d+1)≤1ep(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.

Try It: Resampling in Action

Below is a small instance of the LLL setting: ten binary variables x1,…,x10x_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.

<!-- Moser-Tardos demo: variable row + constraint chips + log -->
<p class="hint">Ten binary variables x1–x10 and eight constraints. Each constraint forbids one specific pattern on three variables. Green = satisfied, red = violated. Run the algorithm or step through it manually.</p>
<div id="var-row" class="var-row" aria-label="Variable values"></div>
<div id="constraints-area" class="constraints-area" aria-label="Constraint status"></div>
<div class="status-bar" id="status">Press Run or Step to start.</div>
<div class="log-box" id="log" aria-label="Resampling log"></div>
<div class="btns">
  <button id="btn-run" type="button">Run Moser-Tardos</button>
  <button id="btn-step" type="button">Step</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>

/* Layout and color coding for variables and constraints */
* { 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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Moser-Tardos resampling algorithm demo
// LLL condition: each constraint touches at most 4 others (well within ep(d+1)<=1)

// Number of binary variables x1..x10
const NUM_VARS = 10;

// Each constraint has: vars = indices of its 3 variables,
// bad = the forbidden pattern (the 'bad event' the constraint represents)
const CONSTRAINTS = [
  { vars: [0,1,2], bad: [1,1,1] },
  { vars: [1,2,3], bad: [0,0,0] },
  { vars: [2,3,4], bad: [1,0,1] },
  { vars: [3,4,5], bad: [0,1,0] },
  { vars: [4,5,6], bad: [1,1,0] },
  { vars: [5,6,7], bad: [0,0,1] },
  { vars: [6,7,8], bad: [1,0,0] },
  { vars: [7,8,9], bad: [0,1,1] },
];

// Algorithm state
let vals = [];
let stepCount = 0;
let running = false;
let done = false;

function randBit(){ return Math.random() < 0.5 ? 0 : 1; }

function initVals(){
  vals = Array.from({ length: NUM_VARS }, () => randBit());
  stepCount = 0;
  done = false;
}

// Find first violated constraint (bad event that occurred)
function findViolated(){
  return CONSTRAINTS.find(c =>
    c.vars.every((vi, i) => vals[vi] === c.bad[i])
  ) || null;
}

// Check if all constraints are satisfied
function allSatisfied(){
  return CONSTRAINTS.every(c =>
    !c.vars.every((vi, i) => vals[vi] === c.bad[i])
  );
}

// Render variables and constraint chips; highlight resampled vars
function render(highlighted){
  const row = document.getElementById('var-row');
  row.innerHTML = '';
  vals.forEach((v, i) => {
    const d = document.createElement('div');
    d.className = 'var-box val-' + v + (highlighted && highlighted.includes(i) ? ' resampled' : '');
    d.title = 'x' + (i+1) + ' = ' + v;
    d.textContent = 'x' + (i+1);
    row.appendChild(d);
  });

  const area = document.getElementById('constraints-area');
  area.innerHTML = '';
  CONSTRAINTS.forEach((c, ci) => {
    const violated = c.vars.every((vi, i) => vals[vi] === c.bad[i]);
    const d = document.createElement('div');
    d.className = 'c-chip ' + (violated ? 'violated' : 'satisfied');
    d.title = fmt('Bad pattern: %map%', { map: c.vars.map((vi,i) => 'x'+(vi+1)+'='+c.bad[i]).join(', ') });
    d.textContent = 'C' + (ci+1);
    area.appendChild(d);
  });
}

function setStatus(t, cls){
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status-bar ' + (cls||'');
}

function addLog(msg){
  const lb = document.getElementById('log');
  const line = document.createElement('div');
  line.textContent = msg;
  lb.appendChild(line);
  lb.scrollTop = lb.scrollHeight;
}

// One resampling step: find a violated constraint and resample its variables
function doStep(){
  if(done) return;
  const c = findViolated();
  if(!c){
    done = true;
    render([]);
    setStatus('✓ All constraints satisfied!', 'ok');
    addLog(fmt('Done in %stepCount% resampling steps.', { stepCount: stepCount }));
    document.getElementById('btn-step').disabled = true;
    return true;
  }
  // Resample all variables of the violated constraint independently
  c.vars.forEach(vi => { vals[vi] = randBit(); });
  stepCount++;
  render(c.vars);
  addLog(fmt('Step %stepCount%: resampled %map%', { stepCount: stepCount, map: c.vars.map(vi=>'x'+(vi+1)).join(',') }));
  if(allSatisfied()){
    done = true;
    setStatus('✓ All constraints satisfied!', 'ok');
    addLog(fmt('Done in %stepCount% resampling steps.', { stepCount: stepCount }));
    document.getElementById('btn-step').disabled = true;
    return true;
  }
  setStatus(fmt('Running… step %stepCount%', { stepCount: stepCount }), 'running');
  return false;
}

function reset(){
  running = false;
  initVals();
  render([]);
  document.getElementById('log').innerHTML = '';
  setStatus('Press Run or Step to start.', '');
  document.getElementById('btn-step').disabled = false;
}

document.getElementById('btn-run').addEventListener('click', () => {
  if(running) return;
  if(done){ reset(); }
  running = true;
  setStatus(fmt('Running… step %stepCount%', { stepCount: 0 }), 'running');
  addLog('--- Starting new run ---');
  // Animated loop: one step every 160ms
  function tick(){
    if(!running){ return; }
    const finished = doStep();
    if(!finished){ setTimeout(tick, 160); }
    else { running = false; }
  }
  tick();
});

document.getElementById('btn-step').addEventListener('click', () => {
  if(done){ return; }
  if(stepCount === 0){ addLog('--- Starting new run ---'); }
  doStep();
});

document.getElementById('btn-reset').addEventListener('click', reset);

// Initialize on load
reset();
Result
Console

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.

The Real Complexity

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)≤1ep(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 n⋅p1−ep(d+1)\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)≤1ep(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.

Where It Matters

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

  • kk-SAT: a random assignment to a kk-CNF formula with at most 2k/(ek)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 (Δ+1)(\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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/moser-tardos/Content licensed under CC BY-NC 4.0.