Group:Student Seminar
Title: The Constructive Proof of the Lovasz Local Lemma
Speaker: Chengu Wang Tsinghua university
Time: 2010-04-15 16:00-2010-04-15 17:00
Venue: FIT 1-222


The Lovasz Local Lemma (LLL) is an extremely powerful tool in probablility theory that states that the probability that none of a set of bad events happends is nonzero if for each event the number of events that depend on it is rare. The technique can directly be applied to the satisfiability problem, yielding that a k-CNF formula in which each clause has common variables with at most 2^{k-2} other clauses is always satisfiable. However, the proof of LLL doesn't give an algorithm to find an assigment to the k-SAT problem. In STOC'09, Robin Moser gave a randomized algorithm. And in SODA'10, K. Chandrasekaran, N. Goyal and B. Haeupler derandomized it.

In this talk, I will give the non-constructive proof for the k-SAT problem first, and then show the randomized constructive proof by Robin Moser.

Short Bio: