Sunday, January 24, 2010

Recent constructive results for the Lovász Local Lemma

The Lovász Local Lemma is a workhorse in probabilistic combinatorics which has found applications to packet routing, perfect hashing, graph coloring, scheduling, statistical mechanics, etc. It is typically used in conjunction with the probabilistic method to prove the existence of solutions. Efficiently finding these solutions has been the pursuit of a good deal of research, which chipped away at the problem through special cases.

At STOC 2009, Robin Moser resolved an important special case - bounded occurrence k-SAT - with a ZPP algorithm and a weak derandomization. This was an important result in of itself, earning the Best Paper award, but what really tickled the theory community was the marvelous proof strategy he came up with for his talk; "one of the best STOC talks ever", says Uncle Lance. A few months later, he and Gábor Tardos generalized the result to cover (essentially) the entire LLL. Karthekeyan Chandrasekaran, Navin Goyal, and Bernhard Haeupler strengthened the derandomization under a mild "ϵ-slack" condition, thus placing more non-constructive solutions squarely in P. A couple weeks ago, Bernhard Haeupler, Barna Saha, and Aravind Srinivasan showed that the Moser-Tardos algorithm retains a beneficial property of the naive rejection sampling algorithm, which can lead to polynomial running time even with superpolynomial events.

In my talk, we'll touch on each of these results, though much more emphasis will be placed on those by Moser and Tardos. Here's an outline.

  1. (5-10 min) Introduction.
  2. (10-15 min) Proof of symmetric k-SAT LLL from this survey article.
  3. (10 min) A motivational application to hypergraph coloring from Rajmohan Rajaraman's notes.
  4. (5 min) A brief history of results inching towards a constructive proof.
  5. (25-35 min) The Moser-Tardos algorithm for symmetric, bounded occurrence k-SAT and the slick STOC proof as explicated by Fortnow and Tao. (The latter post is excellent.)
  6. (25-30 min) The Moser-Tardos algorithm for symmetric LLL and its proof from Joel Spencer's notes. This proof is more pedestrian but also more general, and it sets up the rest of the talk.
  7. (10 min) Break.
  8. (15-20 min) Derandomization results (briefly).
  9. (10-15 min) Conditional LLL distributions (briefly).

You may wish to review Shannon entropy and derandomization by conditional probability.

1 comment:

  1. Thanks Shiva.

    The Moser proof reminds me quite strongly of "Razborov's proof" of the famous Switching Lemma. See, e.g.,

    I wonder if it's possible to rephrase this Switching Lemma proof in the Moser style.