# Improved Bounds for Sampling Solutions of Random CNF Formulas

arXiv: https://arxiv.org/abs/2207.11892 · HTML: https://mlsanity.com/paper/2207.11892/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jul 2022.

## Built on by (most cited first, 1 of 1)

- [Learning Hard-Constrained Models with One Sample](https://mlsanity.com/paper/2311.03332/) (2023)

## Abstract (arXiv)

Let Phi be a random k-CNF formula on n variables and m clauses, where each clause is a disjunction of k literals chosen independently and uniformly. Our goal is to sample an approximately uniform solution of Phi (or equivalently, approximate the partition function of Phi). Let α=m/n be the density. The previous best algorithm runs in time n^mathsfpoly(k,α) for any αlesssim2k/300 [Galanis, Goldberg, Guo, and Yang, SIAM J. Comput.'21]. Our result significantly improves both bounds by providing an almost-linear time sampler for any αlesssim2k/3. The density α captures the average degree in the random formula. In the worst-case model with bounded maximum degree, current best efficient sampler works up to degree bound 2k/5 [He, Wang, and Yin, FOCS'22 and SODA'23], which is, for the first time, superseded by its average-case counterpart due to our 2k/3 bound. Our result is the first progress towards establishing the intuition that the solvability of the average-case model (random k-CNF formula with bounded average degree) is better than the worst-case model (standard k-CNF formula with bounded maximal degree) in terms of sampling solutions.