{
  "abstract": "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.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2610.10474",
  "author_total": 3,
  "authors": [
    {
      "name": "Kun He"
    },
    {
      "name": "Zhidan Li"
    },
    {
      "name": "Kuan Yang"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/39cm09j6dncya.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2610.10474",
  "fulltext_url": null,
  "id": "39cm09j6dncya",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2610.10474",
  "language": null,
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.DM"
    ],
    [
      "arxiv",
      "cs.DS"
    ],
    [
      "arxiv",
      "math.PR"
    ],
    [
      "openalex",
      "1705|Constraint Satisfaction and Optimization"
    ]
  ],
  "openalex": "W7221027936",
  "pdf_url": "https://arxiv.org/pdf/2610.10474",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-07",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/39cm09j6dncya.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:27:42Z",
      "native_id": "2610.10474",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2610.10474"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.PR",
      "subfield": "probability"
    }
  ],
  "title": "Fast Almost-Uniform Sampling of Random $k$-SAT Solutions",
  "title_text": "Fast Almost-Uniform Sampling of Random k-SAT Solutions",
  "type": "preprint",
  "updated_at": "2026-11-04T15:21:12Z",
  "url": "https://research.draconitic.com/paper/39cm09j6dncya",
  "venue": "arXiv",
  "versions": []
}