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 (1)
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
This page was built for publication: Solving and sampling with many solutions: Satisfiability and other hard problems
