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.

Tuesday, January 12, 2010

Read this blog

This is the class blog for CMU's Spring 2010 graduate CS course 15-859U, "Theoretical Computer Science's Greatest Hits, 2009". 

This is a seminar course. The instructor is Ryan O'Donnell.  The course homepage is, but that page will be mostly static.  Please read this blog regularly, or add it to your RSS feed.  

We will use MathML in these posts; if it is working correctly for you, the following statements should look basically the same:

A set system L is "laminar" if for all A, BL, either AB = Ø, AB, or BA.

A set system $L$ is "laminar" if for all $A$, $B$ $\in$ $L$, either $A \cap B = \emptyset$, $A \subseteq B$, or $B \subseteq A$.

To get this to work, on IE I believe you download an ActiveX control here:

If you use Firefox, try going here:

For Chrome and Safari, I'm not sure; if someone wants to comment on whether or not it works for them, please do.