Fast sampling and counting k-SAT solutions in the local lemma regime

Weiming Feng, Heng Guo, Yitong Yin +1

We give new algorithms based on Markov chains to sample and approximately count satisfying assignments to $k$-uniform CNF formulas where each variable appears at most $d$ times. Fo…