{
  "abstract": "How does a computational problem transition from easy to hard? In the hard-core model, approximate counting and sampling are polynomial-time tractable up to tree uniqueness, but worst-case intractable at any constant relative distance above it unless $\\mathsf{NP}=\\mathsf{RP}$. We quantify the transition from polynomial to exponential mixing for classical Glauber dynamics. On $n$-vertex graphs of maximum degree $d\\ge3$, at fugacity $λ=(1+δ)λ_{\\mathrm c}(d)$ with sufficiently small $δ\\ge0$ that may vanish with $n$, its worst-case mixing time has the form $\\exp\\{Θ(nδ^2/d)\\}n^{1+Θ(1)}$. The upper bound is degree-uniform, and the matching lower bound holds for every fixed $d$. Annealing gives approximate counting with the same running-time upper bound at fixed accuracy. For general sampling and counting algorithms, we establish a robust fine-grained reduction from SAT without assuming a lower bound on SAT's running time. For any fixed $d\\ge3$ and $0<γ<1$, a sampling or approximate-counting algorithm running in $\\exp\\{O((nδ^2/d)^{1-γ})\\}\\operatorname{poly}(n)$ time along any one suitable inverse-polynomial distance sequence $δ=δ(n)$, yields a randomized SAT algorithm running in $\\exp\\{\\widetilde O(s^{1-γ})\\}$ time on inputs of binary length $s$. This power-saving transfer identifies $nδ^2/d$ as the analogue of SAT input length for hard-core sampling and counting at relative distance $δ$ above criticality: beating the Glauber exponent by a fixed power through any sampling or counting method would yield a corresponding power improvement for SAT. At criticality, we establish $O(\\sqrt{n/d})$ spectral independence, optimal in $n$ at fixed degree, and degree-uniform Glauber mixing in $\\widetilde O(n(n/d)^{1+1/(d-2)})$ time, improving the previous $\\widetilde O(n^{4+4/(d-2)})$ bound.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2611.02702",
  "author_total": 3,
  "authors": [
    {
      "name": "Zhe Ju"
    },
    {
      "name": "Jingcheng Liu"
    },
    {
      "name": "Yitong Yin"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/esk4s1q2xm0z1.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2611.02702",
  "fulltext_url": null,
  "id": "esk4s1q2xm0z1",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2611.02702",
  "language": null,
  "licence": "LicenseRef-arXiv-nonexclusive-1.0",
  "licence_label": "arXiv licence",
  "licence_source": "article",
  "licence_url": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.CC"
    ],
    [
      "arxiv",
      "cs.DS"
    ],
    [
      "arxiv",
      "math.PR"
    ]
  ],
  "openalex": null,
  "pdf_url": "https://arxiv.org/pdf/2611.02702",
  "pmcid": null,
  "pmid": null,
  "published": "2026-11-02",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/esk4s1q2xm0z1.ris",
  "sources": [
    {
      "first_seen": "2026-11-03T12:21:10Z",
      "native_id": "2611.02702",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2611.02702"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.PR",
      "subfield": "probability"
    }
  ],
  "title": "Fine-Grained Complexity Across the Computational Phase Transition",
  "title_text": "Fine-Grained Complexity Across the Computational Phase Transition",
  "type": "preprint",
  "updated_at": "2026-11-05T15:20:22Z",
  "url": "https://research.draconitic.com/paper/esk4s1q2xm0z1",
  "venue": "arXiv",
  "versions": []
}