A Kolmogorov complexity proof of the Lovász local lemma for satisfiability
DOI10.1016/J.TCS.2012.06.005zbMATH Open1283.68168OpenAlexW1998096192WikidataQ125052742 ScholiaQ125052742MaRDI QIDQ690463FDOQ690463
Authors: Jochen Messner, Thomas Thierauf 
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Hypergraph colouring and the Lovász local lemma
- An introduction to Kolmogorov complexity and its applications
- An algorithmic approach to the Lovász local lemma. I
- Title not available (Why is that?)
- Asymptotic lower bounds for Ramsey functions
- A constructive proof of the general Lovász local lemma
- A constructive proof of the Lovász local lemma
- Title not available (Why is that?)
- Lopsided Lovász Local lemma and Latin transversals
- On a problem of Spencer
- A parallel algorithmic version of the local lemma
- Title not available (Why is that?)
- Algorithmics
- Disproof of the Neighborhood Conjecture with Implications to SAT
- The Lovász Local Lemma and Satisfiability
Cited In (4)
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 Q690463)
