Improved Bounds for Sampling Solutions of Random CNF Formulas

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.