#
A constructive proof of the general Lovász Local Lemma

## Jack Cheng

The Lovász Local Lemma is a powerful result that asserts the
existence of a certain object which avoids a set of "bad" events.
Earlier proofs for the lemma were nonconstructive, so while the
existence is guaranteed, it is oftentimes unclear how the actual
instance could be constructed. While numerous progress were made on
the problem since Jozsef Beck's breakthrough result in 1991 (which
solved it for a relaxation of the lemma), a constructive proof for the
general Lovász Local Lemma was only discovered recently (2009) by
Moser and Tardos. We present Moser's very simple algorithm and the
beautiful proof of its correctness.

(Based on a paper by
Robin A. Moser in STOC 2009.)