How to Learn the Moser–Tardos Resampling Algorithm: Bad Events, Dependency Graphs, Witness Trees and Constructive Lovász Local Lemma

Wait, What?

A proof that “a good configuration must exist” can sometimes be turned into an algorithm that simply keeps repairing the bad parts.

The Lovász Local Lemma is one of the most striking ideas in probabilistic combinatorics. It says, roughly, that if undesirable events are individually unlikely and do not depend on too many other events, then there is a positive probability that none of them happens. For decades, the theorem was famous partly because it could prove existence without telling you how to find the desired object.

The Moser–Tardos breakthrough changed that for a broad variable-based setting. Their algorithm starts with a random assignment. Whenever a bad event is currently true, it resamples exactly the independent variables that determine that event. Then it keeps going. Under the Local Lemma conditions, this astonishingly simple repair process has a rigorous expected running-time guarantee.

At beginner level, this is a lesson about local repair. At professional level, it becomes a lesson in modelling bad events, dependency structure, randomized algorithms, termination arguments, witness trees, reproducibility and the difference between a theorem’s assumptions and a program’s engineering constraints.

Quick Answer

Learn Moser–Tardos in this order: random variables → bad events → dependency → Local Lemma intuition → resample a violated event → repeat until none remain → witness-tree accounting → expected resampling bounds → implementation data structures → applications → parallel/generalised variants → professional validation.

1. Begin with a concrete constraint problem

Suppose you randomly assign colours to vertices of a graph and want to avoid a collection of forbidden local patterns. Each forbidden pattern can be represented as a bad event. A bad event depends only on the random variables needed to describe that pattern.

If two bad events depend on disjoint sets of independent variables, they are independent in the variable model. If they share a variable, they may influence one another.

This “which variables does each event touch?” question is the structural heart of the algorithm.

2. The Local Lemma is about sparse dependency, not just small probability

It is not enough that each bad event is rare. If one event is entangled with almost every other event, the system can still be difficult.

The useful regime is: each bad event has sufficiently small probability compared with the number and strength of its dependencies. In the symmetric textbook form, one often sees a condition of the shape e p (d + 1) ≤ 1, where p bounds bad-event probability and d bounds dependencies.

The full asymmetric Local Lemma is more general, but the beginner should first understand the structural message: rare locally dependent failures can often be avoided simultaneously.

3. The variable model makes the theorem algorithmic

Moser and Tardos consider bad events determined by mutually independent random variables. Write the variables as:

X1, X2, ..., Xn

Each bad event A has a scope:

vars(A) = variables whose values determine whether A occurs

Two events are adjacent in the dependency graph when their scopes overlap.

This is much more than notation. It tells the algorithm exactly what to resample.

4. The algorithm itself is almost suspiciously simple

sample every independent variable once

while some bad event A is true:
    resample every variable in vars(A)

return the final assignment

That is the conceptual Moser–Tardos algorithm.

The difficulty lies not in writing the loop. It lies in proving that the loop is expected to stop quickly under the correct conditions, and in implementing violation detection efficiently enough that the theoretical insight survives contact with real workloads.

5. Why local resampling is better than restarting everything

A naive approach might generate a completely new random assignment whenever any constraint fails. That throws away all the choices that were already fine.

Moser–Tardos instead repairs only the variables involved in a currently violated event. This is a local update. The new values can fix that event but may activate neighbouring bad events, so the process continues.

The algorithm accepts this possibility. It does not require monotonic progress in the number of violated events at every step.

6. An event can come back

A beginner often assumes that once a bad event is repaired it stays repaired. Not so.

Suppose events A and B share variable X7. Resampling B may change X7 and cause A to become true again.

The analysis therefore cannot be based on “each event is fixed once.” It must account for histories of interacting resamplings.

7. Dependency graphs explain where interference can travel

Create one node per bad event. Connect two nodes when the events share at least one variable.

This graph is not the same as the graph of the original application. It is a graph of failure dependencies.

In a scheduling problem, an original job graph and the bad-event dependency graph may be very different objects. Professionals should name these representations separately to avoid reasoning mistakes.

8. Witness trees are the analysis lens

Moser–Tardos analysis uses witness trees to encode which previous resamplings could have contributed to a later resampling. A node in the tree is labelled by a bad event. Parent–child relationships record dependency relationships relevant to the history.

The crucial insight is that the probability of a particular proper witness tree occurring can be bounded using the probabilities of its event labels. Summing those bounds controls the expected number of resamplings.

You do not need witness trees to run the basic algorithm. You need them to understand why the algorithm is not merely a hopeful heuristic.

9. The algorithm is randomized, but the guarantee is mathematical

Randomness does not mean “uncontrolled.” Under the Local Lemma criteria, the expected number of resamplings is bounded.

The guarantee depends on the model being correct: truly independent base variables, accurately defined bad-event scopes and probability/dependency conditions that actually hold.

If those assumptions are false, the theorem cannot rescue the implementation.

10. A tiny hand example

Imagine three independent bits X1, X2, X3. Define:

A = (X1 = 1 and X2 = 1)
B = (X2 = 0 and X3 = 0)

A and B depend because both use X2.

If A is true, resample X1 and X2. If B is true, resample X2 and X3. Continue until neither event is true.

This example is too small to showcase the full theorem, but it makes the mechanics visible.

11. Event selection policy can vary

The core theorem does not require a magical global priority rule. One can choose an arbitrary currently true bad event, provided the process conforms to the variable-resampling model.

Implementations, however, may benefit from deterministic tie-breaking, priority queues or locality-aware selection because event detection and cache behaviour matter.

Separate theorem-level freedom from engineering-level performance choices.

12. Efficient violation detection is often the real implementation problem

A literal implementation that rescans every bad event after every resampling may be unusably slow.

Instead, maintain an incidence structure:

variable -> bad events that depend on that variable

When event A is resampled, only variables in vars(A) change. Therefore only events incident to those variables can have changed truth value.

This local update principle is what allows the mathematical locality to become computational locality.

13. A practical queue-based skeleton

sample all variables
find currently violated bad events and enqueue them

while queue not empty:
    A = pop a violated event
    if A is no longer violated:
        continue

    changed = vars(A)
    resample(changed)

    for each event B touching any variable in changed:
        if B is violated:
            enqueue B

Production code must also prevent pathological duplicate queue growth, define random-number handling and record sufficient trace information for reproducibility.

14. Random seeds are part of the experiment

If a run unexpectedly performs many resamplings, record the seed. Without it, the difficult execution may be impossible to reproduce.

A professional run record should include at least:

instance identifier;
algorithm/model version;
random seed;
number of variables and bad events;
dependency statistics;
resampling count;
elapsed time;
final validation result.

15. Validate the final state independently

Do not trust the fact that the event queue is empty. Run an independent final pass over all constraints and prove that no bad event remains true.

This catches bookkeeping bugs, stale-cache errors and incorrect incremental updates.

The final validator should be simpler than the incremental engine whenever possible.

16. The Local Lemma condition is not a runtime benchmark

The theorem tells you a regime where expected termination is controlled. It does not tell you the exact wall-clock cost on your machine.

Real cost also depends on:

how expensive each bad event is to evaluate;
how many events touch each variable;
queue behaviour;
random-generation cost;
memory locality;
parallel contention;
distribution of hard instances.

Benchmark those separately.

17. Parallel versions are possible but need careful reasoning

The Moser–Tardos framework inspired parallel algorithmic Local Lemma work. Independent or suitably non-conflicting violated events may be handled concurrently, but careless simultaneous resampling can invalidate assumptions or introduce races in the implementation.

A parallel program must distinguish mathematical independence from mere thread-level separation.

18. Partial resampling is a later generalisation

Subsequent research developed partial-resampling frameworks in which one may resample only part of the variables associated with a bad event. This can improve applications where full resampling is wasteful.

Learn the original full-variable algorithm first. Generalisations make more sense after the dependency and witness-tree ideas are secure.

19. Common application families

Algorithmic Local Lemma techniques appear in combinatorial constructions involving colourings, scheduling, packet routing, graph structures, transversals and satisfiability-like systems.

The reusable pattern is not “use Moser–Tardos for everything.” It is:

independent random choices
+ local bad events
+ sparse dependency
+ local resampling

20. How to teach this from beginner to professional

Use visible state before abstraction:

Predict: given a small assignment, identify which bad events are true.
Run: resample one violated event with a fixed seed.
Investigate: draw the dependency graph and trace which events can change.
Modify: change one bad-event scope and observe the new dependency structure.
Make: implement a queue-based solver with final validation and reproducible seeds.

This progression aligns with programming-education work that supports code reading, tracing, worked examples and gradually reduced scaffolding before independent construction.

21. A good classroom trace table

step | chosen bad event | variables resampled | newly true events | newly false events | seed state

Students should explain every change using shared variables, not vague language such as “the algorithm got luckier.”

22. Professional proof obligations

Before relying on the method, be able to answer:

What are the independent base variables?
Exactly which variables determine each bad event?
What dependency graph follows from those scopes?
Which Local Lemma criterion are you using?
Why does your event-probability bound hold?
Does the implementation resample exactly the intended variables?
Does incremental event detection agree with a full validator?

23. Common failure states

Calling events independent because they “look unrelated” while they share a variable.
Using correlated base variables but analysing them as independent.
Resampling a superset or subset of variables without checking whether the theorem still applies.
Rescanning every event after every step and then blaming the algorithm for poor speed.
Failing to record random seeds.
Treating expected running time as a worst-case wall-clock guarantee.
Stopping when the queue is empty without independent final validation.
Quoting the Local Lemma condition without showing how the application satisfies it.

24. Practice ladder

Beginner: identify bad events and shared variables in tiny examples.
Foundation: implement naive resampling and full rescanning.
Intermediate: add dependency-based incremental updates and seed logging.
Advanced: derive probability/dependency bounds and study witness trees.
Professional: build a validated solver with workload instrumentation, parallelism experiments, adversarial cases and theorem-to-code assumption checks.

25. Ownership boundary

This article owns the Moser–Tardos resampling algorithm as a learning object: variable models, bad events, dependency, local resampling, witness-tree reasoning, implementation and validation. It does not replace general probability theory, satisfiability solving, distributed scheduling, learner measurement or private system architecture.

Sources and further reading

Robin A. Moser and Gábor Tardos, “A Constructive Proof of the General Lovász Local Lemma,” Journal of the ACM 57(2), 2010: DOI.
David G. Harris and Aravind Srinivasan, “The Moser–Tardos Framework with Partial Resampling,” Journal of the ACM 66(5), 2019: DOI.
Nicholas J. A. Harvey and Jan Vondrák, “An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles,” SIAM Journal on Computing 49(2), 2020: DOI.
ACM/IEEE-CS/AAAI CS2023, Algorithmic Foundations: CS2023.
Sue Sentance, Jane Waite and Maria Kallia, PRIMM programming pedagogy: SIGCSE 2019.

Professional rule: you understand Moser–Tardos when you can model the independent variables and bad-event scopes correctly, explain why local resampling can revisit earlier failures, connect the expected-work guarantee to the Local Lemma assumptions, and verify the final assignment independently of the incremental bookkeeping.

Small Group Tutorials