Fast Almost-Uniform Sampling of Random k-SAT Solutions

arXiv:2610.10474 · cs.DS, cs.DM, math.PR · Submitted 2026-10-07 · Read on arXiv

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