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 $\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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Computational Complexity

• arXiv preprint · 3 November 2026

  State Evolution and Universality of Iterated Linear Programs for the Binary Perceptron

  Jianan Zhang and Shuangping Li
• arXiv preprint · 2 November 2026

  On a Class of Non-Local Elliptic-Transport Systems in Score-Guided Probability Flow on $SE(3)$: Score-Singularity Resolution, Space-Time ADN Shift, and Markov Mean-Field Games

  Pilhwa Lee
• arXiv preprint · 3 November 2026

  A Bayesian-Geometric Reading of Classical Model-Based Optimal Design

  Mohamed Tarek
• arXiv preprint · 2 November 2026

  Online Algorithms Cannot Find Isolated Perceptron Solutions

  Shuangping Li and Gabe Schoenbach
• arXiv preprint · 3 November 2026

  Glauber Dynamics for Sampling Colorings: Rapid Mixing above $(1+1/\mathrm{e})Δ$ via Hidden Hard-Core Models

  Xiongxin Yang

All new papers in Computational Complexity