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

DOI10.1007/978-3-642-22685-4_15zbMATH Open1353.68146OpenAlexW151625577MaRDI QIDQ3087948FDOQ3087948

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

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

Mathematics Subject Classification ID

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

Cited In (6)

• Probabilistic constructions of computable objects and a computable version of Lovász local lemma
• A Kolmogorov complexity proof of the Lovász local lemma for satisfiability
• 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)