The local lemma is tight for SAT

MaRDI QIDQ5365071zbMATH OpenFDO

Authors Heidi Gebauer, Tibor Szabó, Gábor Tardos

Publication date 29 September 2017

Full work available at URL http://dl.acm.org/citation.cfm?id=2133088

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial probability (60C05)

Recommendations

• The local lemma Is asymptotically tight for SAT
• A constructive proof of the Lovász local lemma
• The Lovász Local Lemma and Satisfiability
• Theory and Applications of Models of Computation
• A Note on Unsatisfiable k-CNF Formulas with Few Occurrences per Variable

Cited in

(11)

• An algorithmic proof of the Lovász local lemma via resampling oracles
• A Kolmogorov complexity proof of the Lovász local lemma for satisfiability
• Satisfiability with index dependency
• Disproof of the neighborhood conjecture with implications to SAT
• An algorithmic construction of union-intersection-bounded families
• Disproof of the Neighborhood Conjecture with Implications to SAT
• The Lovász Local Lemma and Satisfiability
• Combinatorial constructions of separating codes
• On Local Versus Global Satisfiability
• A Complexity Dichotomy for the Coloring of Sparse Graphs
• The local lemma Is asymptotically tight for SAT

This page was built for publication: The local lemma is tight for SAT

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