Counting random $k$-SAT near the satisfiability threshold

Zongchen Chen, Aditya Lonkar, Chunyang Wang +2

We present efficient counting and sampling algorithms for random $k$-SAT when the clause density satisfies $\alpha \le \frac{2^k}{\mathrm{poly}(k)}.$ In particular, the exponential term…