Improved Bounds for Sampling Solutions of Random CNF Formulas

DOI10.1137/1.9781611977554.CH128arXiv2207.11892OpenAlexW4316652433MaRDI QIDQ6405895FDOQ6405895

Authors: Kun He, Kewen Wu, Kuan Yang 

Publication date: 24 July 2022

Abstract: 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 $alpha=m/n$ be the density. The previous best algorithm runs in time $n^{mathsfpoly(k,alpha)}$ for any $alphalesssim{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 $alphalesssim{2}^{k/3}$. The density $alpha$ captures the emph{average degree} in the random formula. In the worst-case model with bounded emph{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 average-case 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.

Full work available at URL: https://doi.org/10.1137/1.9781611977554.ch128

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cited In (1)

• Fast sampling of satisfying assignments from random \(k\)-SAT with applications to connectivity

This page was built for publication: Improved Bounds for Sampling Solutions of Random CNF Formulas

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6405895)