{"id":"arxiv/2610.10474","url":"https://arxiv.org/abs/2610.10474","tags":["cs.DS","cs.DM","math.PR"],"score":0,"title":"Fast Almost-Uniform Sampling of Random $k$-SAT Solutions","domain":"cs.DS","source":"arxiv","authors":["Kun He","Zhidan Li","Kuan Yang"],"reviews":0,"subject":"cs.DS","summary":"We study approximately uniform sampling of satisfying assignments from random $k$-SAT formulas. For every sufficiently large $k$ and density $0 < α\\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 the uniform distribution on satisfying assignments and whose expected running time is at most $(nk(α+1)/\\varepsilon)^C$, for a universal constant $C$. Our algorithm improves the counting and sampling algorithms obtained by Chen, Lonkar, Wang, Yang, and Yin (STOC 2025) at the…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-07","reactions":{}}