Counting random k-SAT near the satisfiability threshold

Abstract

We present efficient counting and sampling algorithms for random $k$-SAT when the clause density satisfies $\alpha \leq 2^k/\text{poly}(k)$. In particular, the exponential term $2^k$ matches the satisfiability threshold $\Theta(2^k)$ for the existence of a solution and the (conjectured) algorithmic threshold $2^k(\ln k)/k$ for efficiently finding a solution. Previously, the best-known counting and sampling algorithms required far more restricted densities $\alpha\lesssim 2^k/3$ [He, Wu, Yang, SODA ‘23]. Notably, our result goes beyond the lower bound $d\gtrsim 2^k/2$ for worst-case $k$-SAT with bounded-degree $d$ [Bezáková et al, SICOMP ‘19], showing that for counting and sampling, the average-case random $k$-SAT model is computationally much easier than the worst-case model. At the heart of our approach is a new refined analysis of the recent novel coupling procedure by [Wang, Yin, FOCS ‘24], utilizing the structural properties of random constraint satisfaction problems (CSPs). Crucially, our analysis avoids reliance on the $2$-tree structure used in prior works, which cannot extend beyond the worst-case threshold $2^k/2$. Instead, we employ a witness tree similar to that used in the analysis of the Moser-Tardos algorithm [Moser, Tardos, JACM ‘10] for the Lovász Local lemma, which may be of independent interest. Our new analysis provides a universal framework for efficient counting and sampling for random atomic CSPs, including, for example, random hypergraph colorings. At the same time, it immediately implies as corollaries several structural and probabilistic properties of random CSPs that have been widely studied but rarely justified, including replica symmetry and non-reconstruction.

Publication
to appear in The 57th ACM Symposium on Theory of Computing (STOC 2025)
Zongchen Chen
Zongchen Chen
Assistant Professor

I am an assistant professor in the School of Computer Science at Georgia Tech. I have broad interests in randomized algorithms, discrete probability, and machine learning. Currently, my research focuses on Markov chain Monte Carlo (MCMC) methods, approximate counting and sampling, and learning and testing of high-dimensional distributions.

Chunyang Wang
Chunyang Wang
Ph.D Student

I am currently a fifth-year Ph.D student in the Theory Group in the Department of Computer Science and Technology at Nanjing University. My research interest lies in a broad aspect of computer science. Currently, I am focusing on algorithms for counting and sampling.

Kuan Yang
Kuan Yang
Assistant Professor

I am an assistant professor in the John Hopcroft Center for Computer Science at Shanghai Jiao Tong University. I am interested in many aspects of theoretical computer science, discrete probability and combinatorics. Currently I mainly work on designing and analysing approximation algorithms for counting and sampling problems.

Yitong Yin
Yitong Yin
Professor

I am a professor in the Theory Group in the Department of Computer Science and Technology at Nanjing University. I am interested in Theoretical Computer Science.