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

DOI10.1016/j.tcs.2012.06.005zbMath1283.68168OpenAlexW1998096192WikidataQ125052742 ScholiaQ125052742MaRDI QIDQ690463

Thomas Thierauf, Jochen Messner

Publication date: 27 November 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.06.005

zbMATH Keywords

Kolmogorov complexitysatisfiabilityLovász local lemma

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lopsided Lovász Local lemma and Latin transversals
• On a problem of Spencer
• Asymptotic lower bounds for Ramsey functions
• Hypergraph colouring and the Lovász local lemma
• A constructive proof of the general lovász local lemma
• Disproof of the Neighborhood Conjecture with Implications to SAT
• The Lovász Local Lemma and Satisfiability
• An algorithmic approach to the Lovász local lemma. I
• A parallel algorithmic version of the local lemma
• A constructive proof of the Lovász local lemma
• An introduction to Kolmogorov complexity and its applications

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