Improved Bounds for Sampling Solutions of Random CNF Formulas

Kun He, Kewen Wu, Kuan Yang

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 a…