ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-018 | 8th February 2011 12:23

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

RSS-Feed




TR11-018
Authors: Jochen Messner, Thomas Thierauf
Publication: 11th February 2011 10:04
Downloads: 2742
Keywords: 


Abstract:

Recently, Moser and Tardos [MT10] 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.



ISSN 1433-8092 | Imprint