Algorithmic proof of the Lovasz Local Lemma via resampling oracles

Computer Science/Discrete Mathematics Seminar II
Topic:Algorithmic proof of the Lovasz Local Lemma via resampling oracles
Speaker:Jan Vondrák
Affiliation:IBM Almaden Research Center; Member, School of Mathematics
Date:Tuesday, October 27
Time/Room:10:30am - 12:30pm/S-101
Video Link:

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.