Fine-Grained Complexity Across the Computational Phase Transition

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)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((nδ²/d)1-γ)(n) time along any one suitable inverse-polynomial distance sequence $δ=δ(n)$, yields a randomized SAT algorithm running in exp\ O(s1-γ)\ 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(n4+4/(d-2)) bound.