Title: Deterministic Algorithms for the Lovasz Local Lemma
Speaker: Navin Goyal, Microsoft Research India
Date: Wednesday, November 17, 2010 11:00-12:00pm
Location: CoRE Bldg, CoRE 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Lovasz Local Lemma is a powerful tool in probability theory asserting that the probability that none of a set of bad events happen is nonzero if the probability of each event is small compared to the number of events that depend on it. The local lemma finds applications in a wide variety of problems. It's used to show the existence of objects such as satisfying assignments of certain Boolean formulas, or an efficient packet routing scheme in a network. However, the original proof of the local lemma only proves the existence, and does not provide an efficient algorithm to construct such objects. A steady line of work on making the local lemma algorithmic recently culminated in the work of Moser and of Moser--Tardos, who gave an efficient randomized algorithm for a general version of the local lemma. More recently, with Karthekeyan Chandrasekaran and Bernhard Haeupler we found a deterministic algorithm for a fairly general version of the local lemma. In this talk, I will describe this deterministic algorithm. [This work appeared in SODA'10.]