Title: Algorithmic Proof of The Lovasz Local Lemma Via Resampling Oracles
Speaker: Jan Vondrak, IBM/IAS
Date: Monday, November 2, 2015 2:00 pm
Location: Hill Center, Room 425, Rutgers University, Busch Campus, Piscataway, NJ
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, using what we call "resampling oracles". 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.
(joint work with Nick Harvey)
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math