讨论组:学生讲座
标题:The Constructive Proof of the Lovasz Local Lemma
演讲人: 王晨谷 清华大学
时间: 2010-04-15 16:00-2010-04-15 17:00
地点: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.




人物介绍: