Research map / Learning theory and algorithms / Sample complexity
Closing the Gap Between Short and Long XORs for Model Counting
Shengjia Zhao, Sorathan Chaturapruek, Ashish Sabharwal, Stefano Ermon
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 short parity constraints (small f) for upper bounds instead of provable minimum f* | Sparse XOR bounds · Darwin's Finches | lower bound log2: f=0.03 vs f*=0.18; LB 53 vs true 55.90 | Improved |
| compute new sparse-XOR upper bound instead of trivial bound | contingency tables · Darwin's Finches | upper bound log2: 204 -> 150 | Improved |
| compute new sparse-XOR upper bound instead of trivial bound | contingency tables · iqd | upper bound log2: 76 -> 17 | Improved |
| compute new sparse-XOR upper bound instead of trivial bound | contingency tables · synth_20 | upper bound log2: 400 -> 14 | Improved |
| use sparse XOR bounds (one solution per iteration) instead of ApproxMC long XORs | model counting · ANOR2011 runtime | runtime (s): 3800 -> 43571 (UB f=0.5 vs ApproxMC) on wff.3.150.525 | Improved |
| reduce constraint density f from 0.5 to small values (ablation) | Sparse XOR bounds · Langford12 | upper bound tightness | Hurt |
| reduce constraint density f (ablation) | Sparse XOR lower bound · Langford12 | lower bound | No clear effect |
| use long XORs (f=0.5) via ApproxMC on hard instances | ApproxMC · lang15, ls8, wff.3.100.150, wff.4.100.500, 2bitmax-6 | completion | Hurt |
Closest papers by meaning
- Towards Projected and Incremental Pseudo-Boolean Model Counting (AAAI 2025 · similarity 0.85)
- Towards Real-Time Approximate Counting (AAAI 2025 · similarity 0.85)
- Auditable Algorithms for Approximate Model Counting (AAAI 2024 · similarity 0.85)
- Model Counting and Sampling via Semiring Extensions (AAAI 2024 · similarity 0.84)
- The Gradient of Algebraic Model Counting (AAAI 2025 · similarity 0.84)
- Solving Satisfiability Modulo Counting for Symbolic and Statistical AI Integration with Provable Guarantees (AAAI 2024 · similarity 0.83)
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.
