Fast nearly uniform sampling of solutions for random k-sat problems
Fast Almost-Uniform Sampling of Random $k$-SAT Solutions
Data Structures and AlgorithmsDiscrete Mathematics
Summary
The paper addresses how to quickly find solutions to random k-SAT problems, which are logical puzzles with many variables. The authors design an algorithm that picks solutions almost uniformly at random, even when the problem is large and dense with constraints. Their method runs efficiently with a guaranteed low error, improving on previous approaches that needed much more time. They use sophisticated math tools to separate the problem into parts and sample solutions effectively.
What this means in practice
- •For algorithm engineers: Implement efficient samplers for large-scale constraint satisfaction problems with guaranteed near-uniformity and low runtime.
- •For probabilistic modelers: Generate almost uniformly random solutions in satisfiability models to test hypotheses or simulate complex logical systems.
Authors
Kun He, Zhidan Li, Kuan Yang
Abstract
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 density $2^k/\operatorname{poly}(k)$ with running time $(n/\varepsilon)^{\operatorname{poly}(k,α)}$. Our result achieves this density region for sampling with a polynomial degree independent of both the width and the density. Our algorithm separates a high-degree core from the remaining variables, and combines a recursive sampler for the residual formulas with approximate block heat-bath updates on the core. We adapt the recursive insertion-chain framework of Jain, Mizgerd, and Pham (2026) from $2$-trees to ordinary connected violation sets. Expansion and random literal signs yield uniform moment bounds for the resulting correlated lists across all residual formulas, allowing the signed-flow analysis to give a universal polynomial running-time degree. A polymer expansion and an exploration bound establish a polynomial spectral gap for the core dynamics.