Kun He

Fast Almost-Uniform Sampling of Random $k$-SAT Solutions

We study approximately uniform sampling of satisfying assignments from random $k$-SAT formulas. For every sufficiently large $k$ and density $0<\alpha \le 2^k/k^{16}$, we prove that, with high probability over the formula, there is a sampler whose output distribution is within total variation distance $\varepsilon$ of...