Improved Bounds for Sampling Solutions of Random CNF Formulas

Let Φ 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 Φ (or equivalently, approximate the partition function of Φ).

Let α = m/n be the density. The previous best algorithm runs in time n poly(k,α) for any α 2 k/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 α 2 k/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 2 k/5 [He, Wang, and Yin, FOCS'22 and SODA'23], which is, for the first time, superseded by its averagecase counterpart due to our 2 k/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.