ABSTRACT: The Lovasz Local Lemma [Erd?s, Lovasz, 1975] is a powerful tool
to nonconstructively prove the existence of combinatorial objects meeting
a prescribed collection of criteria. In his breakthrough paper [Beck,
1991], Beck demonstrated that a constructive variant can be given under
certain more restrictive conditions. Simplifications of his method and
relaxations of its restrictions were subsequently exhibited in several
publications [Alon; Molloy, Reed; Czumaj, Scheideler; Srinivasan; M.].
This year, we have been able to demonstrate that for almost all known
applications of the Local Lemma, a randomized algorithm can find the
object guaranteed to exist in polynomial expected time [Tardos, M., 2009],
closing the gap between nonconstructive and constructive versions almost
entirely. Very recently, our algorithm has also been derandomized
[Chandrasekaran, Goyal and Haeupler]. In this talk, I will return to a
previous, somewhat less general version of the algorithm applied to the
problem of finding a satisfying assignment to a k-CNF formula with bounded
size clause neighborhoods and then show how a very simple and short
information theoretic argument can be used to bound the algorithm's
expected running time.

BIO: Robin Moser is a graduate student in Theoretical CS at ETH Zurich,
Switzerland, and this fall he will be an intern in the Theory group. He is
mainly interested in exact algorithms for NP-hard combinatorial problems,
most prominently satisfiability and constraint satisfaction problems. His
work on a constructive proof of the Lovasz Local Lemma won a best-paper
award at the 2009 Symposium on the Theory of Computing (STOC).