A Kolmogorov complexity proof of the Lovász local lemma for satisfiability

DOI10.1007/978-3-642-22685-4_15MaRDI QIDQ3087948zbMATH OpenOpenAlexFDO

Authors Jochen Messner, Thomas Thierauf

Publication date 17 August 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22685-4_15

Mathematics Subject Classification ID

Combinatorial probability (60C05) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• A Kolmogorov complexity proof of the Lovász local lemma for satisfiability
• A constructive proof of the Lovász local lemma
• A constructive proof of the general Lovász local lemma
• Deterministic algorithms for the Lovász local lemma
• Deterministic algorithms for the Lovász local lemma

Cited in

(6)

• A Kolmogorov complexity proof of the Lovász local lemma for satisfiability
• Probabilistic constructions of computable objects and a computable version of Lovász local lemma
• Circuit lower bounds à la Kolmogorov
• On the paper of Pascal Schweitzer concerning similarities between incompressibility methods and the Lovász local lemma
• The Lovász Local Lemma and Satisfiability
• A constructive proof of the Lovász local lemma

This page was built for publication: A Kolmogorov complexity proof of the Lovász local lemma for satisfiability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3087948)