Research map / Learning theory and algorithms / Combinatorial and search optimization
A Sharp Leap from Quantified Boolean Formula to Stochastic Boolean Satisfiability Solving
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use clause selection with integrated model counting to solve general multi-level SSAT | ClauSSat · 318 SSAT formulas | formulas solved exactly: 188 vs. 169 | Helped |
| Use clause selection with integrated model counting to solve two-level SSAT | ClauSSat · 215 two-level SSAT instances | formulas solved exactly: 127 vs. 119 | Helped |
| Use clause selection and model counting rather than the compared solvers | ClauSSat · All evaluated formulas | maximum memory usage (GB): 2.4 vs. 32.1 | Helped |
| Use ClauSSat instead of erSSAT | ToiletA 10 05.3 · ToiletA 10 05.3 | satisfying probability lower bound: 1.56e-2 -> 3.13e-2 | Helped |
| Use ClauSSat instead of erSSAT | MPEC c5315-er · MPEC c5315-er | satisfying probability lower bound: 4.14e-1 -> 3.30e-1 | Hurt |
| Add cube distribution (ablation) | ClauSSat-{m} · All evaluated formulas | formulas solved exactly: +11 formulas | Helped |
| Add cube distribution (ablation) | ClauSSat-{m} · All evaluated formulas | formulas with tighter bounds: +23 formulas | Helped |
| Add non-chronological backtracking (ablation) | ClauSSat-{mc} · All evaluated formulas | formulas solved exactly: +18 formulas | Helped |
| Add non-chronological backtracking (ablation) | ClauSSat-{mc} · All evaluated formulas | formulas with tighter bounds: +34 formulas | Helped |
Closest papers by meaning
- Unifying Decision and Function Queries in Stochastic Boolean Satisfiability (AAAI 2024 · similarity 0.96)
- SharpSSAT: A Witness-Generating Stochastic Boolean Satisfiability Solver (AAAI 2023 · similarity 0.93)
- Lifting (D)QBF Preprocessing and Solving Techniques to (D)SSAT (AAAI 2023 · similarity 0.92)
- Solving Higher-Order Quantified Boolean Satisfiability via Higher-Order Model Checking (AAAI 2025 · similarity 0.88)
- Learning How to Cube (NeurIPS 2026 · similarity 0.86)
- Hardness of Random Reordered Encodings of Parity for Resolution and CDCL (AAAI 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.