The local lemma is tight for SAT

zbMATH Open1373.68270MaRDI QIDQ5365071FDOQ5365071

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

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

Mathematics Subject Classification ID

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

Cited In (11)

• 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
• An algorithmic proof of the Lovász local lemma via resampling oracles

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)