Abstract
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 $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.
Zongchen Chen
Assistant Professor
I am an Assistant Professor in the School of Computer Science at Georgia Tech. My research interests include randomized algorithms, discrete probability, and learning theory.
Chunyang Wang
Postdoc
I am Chunyang Wang (王淳扬), currently a project researcher (postdoc) at the National Institute of Informatics (NII), hosted by Prof. Yuichi Yoshida. My research interests broadly lie in theoretical computer science, especially algorithms for counting and sampling and algorithmic stability.
Kuan Yang
Tenure-track Associate Professor
I am a tenure-track Associate Professor in the John Hopcroft Center for Computer Science at Shanghai Jiao Tong University. My research interests include theoretical computer science, discrete probability, and combinatorics, with a focus on approximation algorithms for counting and sampling problems.
Yitong Yin
Professor
I am a professor in the Theory Group at the School of Computer Science, Nanjing University. My research interests include randomized algorithms and computational sampling and counting, data structures and lower bounds, and parallel and distributed computing.