A Constructive Proof of the Lovasz Local Lemma

Pat Morin

In this talk, I will present one of the most exciting theoretical computer science results of the last year: Robin Moser's breakthrough proof of the Lovasz Local Lemma by a randomized algorithm with polynomial expected running time.

More specifically, I will present the special case of the proof for solving instances of k-SAT in which no variable appears in more than 2^k-O(1)/k clauses.