The Lovász Local Lemma and Satisfiability
From MaRDI portal
Publication:3644712
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
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
