Fine-Grained Complexity Across the Computational Phase Transition

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 NP=RP. We quantify the transition from polynomial to exponential mixing for classical Glauber dynamics. On n-vertex graphs of maximum degree d≥3, at fugacity λ=(1+δ)λ_c(d) with sufficiently small δ≥0 that may vanish with n, its worst-case mixing time has the form exp{Θ(nδ²/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≥3 and 0<γ<1, a sampling or approximate-counting algorithm running in exp{O((nδ²/d)^1−γ)}poly(n) time along any one suitable inverse-polynomial distance sequence δ=δ(n), yields a randomized SAT algorithm running in exp{Õ(s^1−γ)} time on inputs of binary length s. This power-saving transfer identifies nδ²/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(√(n/d)) spectral independence, optimal in n at fixed degree, and degree-uniform Glauber mixing in Õ(n(n/d)^1+1/(d−2)) time, improving the previous Õ(n^4+4/(d−2)) bound.

Analysis of Polynomial Threshold Functions on Random Regular Graphs: Computational Complexity of Detecting Noisy Random Lifts
Xifan Yu
arXiv4 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Computational complexity of static output feedback stabilization
Zhaobo Liu
arXiv3 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
The Computational Complexity of the Ungar Games on Distributive Lattices
Kengo Hashimoto
arXiv7 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
On the Computational Complexity of Hidden Markov Model Identification
Markel Zubia, Nils Jansen
arXiv6 Oct 2026PreprintarXiv licenceFull textStatisticsarXiv
Computational complexity of the H-coloring problem in cubic graphs
Vahan Mkrtchyan
arXiv26 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{ju2026finegrained,
  title = {{Fine-Grained Complexity Across the Computational Phase Transition}},
  author = {Zhe Ju and Jingcheng Liu and Yitong Yin},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.02702},
  eprint = {2611.02702},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.02702},
}

RIS

TY  - UNPB
TI  - Fine-Grained Complexity Across the Computational Phase Transition
AU  - Zhe Ju
AU  - Jingcheng Liu
AU  - Yitong Yin
PY  - 2026
DA  - 2026/11/02
PB  - arXiv
DO  - 10.48550/arxiv.2611.02702
UR  - https://arxiv.org/abs/2611.02702
AB  - 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 NP=RP. We quantify the transition from polynomial to exponential mixing for classical Glauber dynamics. On n-vertex graphs of maximum degree d≥3, at fugacity λ=(1+δ)λ_c(d) with sufficiently small δ≥0 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≥3 and 0<γ<1, a sampling or approximate-counting algorithm running in exp{O((nδ^2/d)^1−γ)}poly(n) time along any one suitable inverse-polynomial distance sequence δ=δ(n), yields a randomized SAT algorithm running in exp{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(√(n/d)) spectral independence, optimal in n at fixed degree, and degree-uniform Glauber mixing in Õ(n(n/d)^1+1/(d−2)) time, improving the previous Õ(n^4+4/(d−2)) bound.
ER  -

Abstract

Related

Cite