Consider conjunctive normal form (CNF) formulas on \(n\)  Boolean variables.
We call a CNF formula \(\Phi \)  a \((k,d)\) -CNF formula if all of its clauses have size \(k\)  and each variable appears in at most \(d\)  clauses.
In [1]}, [2]}, an \(\mathrm {poly}(d,k)\cdot n^{1+2^{-20}}\) -time algorithm is given for sampling almost uniform satisfying solutions under a local lemma condition \(k \ge 20\log k + 20\log d + 60\) .
