The Lovász Local Lemma and Satisfiability

DOI10.1007/978-3-642-03456-5_3zbMath1258.68067OpenAlexW2171001921MaRDI QIDQ3644712

Dominik Scheder, Robin A. Moser, Heidi Gebauer, Ermo Welzl

Publication date: 12 November 2009

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-03456-5_3

Mathematics Subject Classification ID

Classical propositional logic (03B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

Waiter-client and client-waiter colourability and \(k\)-SAT games ⋮ A General Framework for Hypergraph Coloring ⋮ On simplified NP-complete variants of \textsc{Monotone} 3\textsc{-Sat} ⋮ A Kolmogorov complexity proof of the Lovász local lemma for satisfiability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing unsatisfiable \(k\)-SAT instances with few occurrences per variable
• Lopsided Lovász Local lemma and Latin transversals
• A simplified NP-complete satisfiability problem
• Using Lovász local lemma in the space of random injections
• Linear CNF formulas and satisfiability
• On a problem of Spencer
• Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
• An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF
• Homomorphisms of conjunctive normal forms.
• DNF tautologies with a limited number of occurrences of every variable
• On subclasses of minimal unsatisfiable formulas
• New methods for 3-SAT decision and worst-case analysis
• On the chromatic number of set systems
• A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract)
• A Note on Unsatisfiable k-CNF Formulas with Few Occurrences per Variable
• Disproof of the Neighborhood Conjecture with Implications to SAT
• An algorithmic approach to the Lovász local lemma. I
• A parallel algorithmic version of the local lemma
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
• Short proofs are narrow—resolution made simple
• Combinatorial Games
• On a combinatorial problem. II
• An Application of Ramsay's Theorem to a Problem of Erdos and Hajnal
• On Linear CNF Formulas

This page was built for publication: The Lovász Local Lemma and Satisfiability