CS 269S, Spring 2012: Theory Seminar
Bren Hall, Room 1420
May 11, 2012:

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.)