← 研踪 PaperTrailarXiv:2610.10474 · v2
Fast Almost-Uniform Sampling of Random $k$-SAT Solutions
首次提交 2026-10-08 01:35
版本更新 2026-11-03 00:09
雷达观测 2026-11-04 23:41
摘要
We study approximately uniform sampling of satisfying assignments from random $k$-SAT formulas. Fix a constant $B>0$. For every $k\ge 2^{20}$ and density $0<α\le 2^k/k^{16}$, we prove that, with high probability over a random formula on $n$ variables, every accuracy $n^{-B}\le\varepsilon\le 1/2$ admits a sampler whose output distribution is within total variation distance $\varepsilon$ of the uniform distribution on satisfying assignments with expected running time $$\widetilde O_B\left(\mathrm{poly}(k,α+1)n^{2+η}\right),\quad 0<η\le 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/\mathrm{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.
作者备注：A revised version with fast expected running time
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-03 00:09 · 最新观测版本
Fast Almost-Uniform Sampling of Random $k$-SAT Solutions
We study approximately uniform sampling of satisfying assignments from random $k$-SAT formulas. Fix a constant $B>0$. For every $k\ge 2^{20}$ and density $0<α\le 2^k/k^{16}$, we prove that, with high probability over a random formula on $n$ variables, every accuracy $n^{-B}\le\varepsilon\le 1/2$ admits a sampler whose output distribution is within total variation distance $\varepsilon$ of the uniform distribution on satisfying assignments with expected running time $$\widetilde O_B\left(\mathrm{poly}(k,α+1)n^{2+η}\right),\quad 0<η\le 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/\mathrm{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.
查看此版本解读 →查看此版本原文 ↗