Solving and sampling with many solutions: Satisfiability and other hard problems
From MaRDI portal
Publication:5111870
DOI10.4230/LIPIcs.IPEC.2017.11zbMath1443.68069arXiv1708.01122OpenAlexW2745221522MaRDI QIDQ5111870
Jean Cardinal, Jerri Nummenpalo, Ermo Welzl
Publication date: 27 May 2020
Full work available at URL: https://arxiv.org/abs/1708.01122
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Randomized algorithms (68W20) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)
Related Items
Cites Work
- Unnamed Item
- A short implicant of a CNF formula with many satisfying assignments
- Random generation of combinatorial structures from a uniform distribution
- Solving satisfiability in less than \(2^ n\) steps
- A short proof for a theorem of Harper about Hamming-spheres
- A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
- Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT
- A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
- Improved Pseudorandom Generators for Depth 2 Circuits
- A fast deterministic algorithm for formulas that have many satisfying assignments
- Solving and sampling with many solutions: Satisfiability and other hard problems
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- 3-SAT Faster and Simpler---Unique-SAT Bounds for PPSZ Hold in General
- Theory and Applications of Satisfiability Testing
