Counting Solutions to Random CNF Formulas
summary
Gives a polynomial-time algorithm that approximates the number of satisfying assignments Z for random k-CNF when k is large and clause density alpha ≤ 2^{r k} for some small constant r (about 1/300). Combines Moitra-style marking and a coupling linear program to estimate marginals of “good” variables, uses a bootstrap percolation to identify bad components of size O(log n), brute-force enumerates each bad component, and multiplies marginals to produce the estimate; bound is exponential in k but far below the 2^k log 2 satisfiability threshold.
AI-written summary · about
chapters (12)
- 0:00Introduction and logistics
- 0:35K-SAT model overview
- 3:11Algorithmic challenges
- 5:57Proposed approximation method
- 8:30Q&A on approximation theory
- 9:38Moitra's approach to marginals
- 12:44Using linear programming
- 13:50Handling high-degree variables
- 17:41Technical lemmas for LP
- 20:28Dealing with bad variables
- 24:28Conclusion and future work
- 25:33Extended question and answer
related talks
47mExploiting Combinatorial Structure in Constraint Programming: ...
46mConstrained Sampling and Counting
46mPhase Transitions in Random CSPs
18mSAT Beyond Boolean Interpretations
10mSATisfying answers to difficult questions!
58mSmoothed CSP Refutation Is As Easy As Random, For Both Efficient Algorithms And Certificates
52mCounting Solutions to Random Constraint Satisfaction Problems
24mRandom Max-CSPs Inherit Algorithmic Hardness from Spin Glasses