## Algorithmic proof of the Lovasz Local Lemma via resampling oracles

Jan Vondrák

IBM Almaden Research Center; Member, School of Mathematics

October 27, 2015

For a collection of events on a probability space with specified dependencies, the Lovasz Local Lemma ("LLL") gives a sufficient condition for the existence of a point avoiding all the events. Following Moser's discovery of an efficient algorithm for many applications of the Lovasz Local Lemma, there has been extensive research on various extensions of this result. We present a unifying algorithmic proof of the Lovasz Local Lemma (and its stronger variants such as Shearer's Lemma), independent of the underlying probability space.