Robin Moser gave one of the best STOC talks ever in his award-winning
paper
A
Constructive Proof of the Lovász Local Lemma. Not only an
amazing result but also an incredibly inventive simple proof that he
came up with while preparing the talk.
Here is a sketch of Moser's proof written as a Kolmogorov
complexity argument. This is not the full
Lovász
Local Lemma but captures the main principle.
Theorem: Suppose we have a k-CNF formula φ with n variables
and m clauses and each clause shares a variable with at most r other
clauses. Then there is a constant d such that if r < 2
k-d then
φ is satisfiable. Moreover we can find that assignment in time
polynomial in m and n.
Here's the algorithm:
Solve(φ)
Pick a random assignment of φ
While there is an unsatisfiable clause C
Fix(C)
Fix(C)
Replace the variables of C with new random values
While there is clause D that shares a variable with C that is not
satisfied
Fix(D)
Assume Fix(C) always terminates. Every clause that was satisfied
before we called Fix(C) will still remain satisfied and C will also
now be satisfied. So Solve makes at most m calls to Fix.
We need to show all the Fix(C) terminate. Suppose the algorithm makes s Fix calls including all the recursive ones. We will show s
is bounded and thus the algorithm terminates.
Fix a Kolmogorov random string x of length n+sk (random relative to
φ, k, s, r, m and n) and assume the
algorithm uses the first n bits as the initial assignment and
k bits each to replace the variables in each Fix call.
If we know which clause is being fixed, we know the clause is violated
so we know all the bits of this clause and thus we learn k bits of x.
We then replace those bits with another part of x.
So we can describe x by the list of clauses we fix plus the remaining
n bits of the final assignment. We can describe the C such that Fix(C)
is called by Solve by m log m bits and the remaining fixed clauses by
log r + O(1) bits because either it is one of r clauses that
intersects the previous clause or we indicate the end of a recursive
call (keeping track of the recursion stack).
So we must have m log m + s(log r+O(1))+n ≥ n+sk or
s(k-log r-O(1)) ≤ m log m.
To show s is bounded, we need k-log r-O(1) to be positive or
r<2
k-d
for some constant d.
Note this in fact shows s = O(m log m) so the algorithm runs in
polynomial time. We choose the x randomly which with high probability
will be Kolmogorovly random. QED
In the talk, Moser gives the bound r<2
k-3
and in
follow-up
work with Gábor Tardos shows r<2
k/e (e =
2.71…) which is the best that comes out of the original
Lovász Local Lemma.
by Louisa Gilder and 
arrived yesterday. I