Fast Almost-Uniform Sampling of Random k-SAT Solutions
cs.DS, cs.DM, math.PR
Submitted: 2026-10-07
Updated: 2026-11-02
Comments: A revised version with fast expected running time
License: http://creativecommons.org/licenses/by/4.0/
The gist: We study approximately uniform sampling of satisfying assignments from random k-SAT formulas.
Abstract
We study approximately uniform sampling of satisfying assignments from random k-SAT formulas. Fix a constant B>0. For every k at least 2 20 and density 0<α at most 2 k/k 16, we prove that, with high probability over a random formula on n variables, every accuracy n-B at most epsilon at most 1/2 admits a sampler whose output distribution is within total variation distance epsilon of the uniform distribution on satisfying assignments with expected running time O B (poly(k,α+1)n 2+η), 0<η at most 2 16-k. In particular, the exponent of n is 2+O(2-k) while the dependence on the width and density is polynomial with a universal degree. This improves the parameter-dependent polynomial exponent of the sampling algorithm of Chen, Lonkar, Wang, Yang, and Yin (STOC 2025) in the density regime 2 k/poly(k). Our algorithm separates a high-degree core from the remaining variables. Every residual formula on the good variables is a deletion subformula of a common bounded-dependency formula. Adapting the rejection--repair framework of Liu, Wang, Yin, Zhang and Zhou (arXiv 2026), we construct an executable sampler for all such residual formulas using ordinary connected violation sets replacing weighted 2-tree witnesses and use it to simulate approximate block heat-bath updates on the core. To analyze the resulting core chain, we integrate out the good variables, represent the core marginal by an absolutely convergent polymer expansion and combine a component-swap variance comparison with an adaptive exploration bound. Absorbing single-component interactions into the local weights leaves interactions of cluster size at least two; retaining their additional decay gives a spectral gap of at least 1/(2s n 2 12-k) where s counts core components. Together with the residual sampler, this yields the stated running time.
Sources
Related papers
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles