Algorithmic proof of the Lovasz Local Lemma via resampling oracles

Vondrak 2015 10 27

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. As a consequence, we obtain efficient algorithms for the known settings where the LLL applies (independent random variables, random permutations, perfect matchings, spanning trees). We present some new applications, in particular a new result on packings of rainbow spanning trees.