Name
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.tcs.2012.06.005 | Electronic Colloquium on Computational Complexity |
Keywords | DocType | Volume |
sz local lemma,boolean formula,constructive proof,satisfying assignment,syntactic property,local lemma,lovasz local lemma,kolmogorov complexity,kolmogorov complexity proof | Conference | 461, |
ISSN | Citations | PageRank |
0304-3975 | 2 | 0.40 |
References | Authors | |
15 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jochen Messner | 1 | 70 | 4.86 |
| Thomas Thierauf | 2 | 288 | 33.59 |