A Kolmogorov Complexity Proof of the Lovász Local Lemma for Satisfiability

Jochen Messner and Thomas Thierauf

Recently, Moser and Tardos came up with a constructive proof of the Lovász Local Lemma. In this paper, we give another constructive proof of the lemma, based on Kolmogorov complexity. Actually, we even improve the Local Lemma slightly.