{"id":"arxiv/2611.02702","url":"https://arxiv.org/abs/2611.02702","tags":["cs.CC","cs.DS","math.PR"],"score":0,"title":"Fine-Grained Complexity Across the Computational Phase Transition","domain":"cs.CC","source":"arxiv","authors":["Zhe Ju","Jingcheng Liu","Yitong Yin"],"reviews":0,"subject":"cs.CC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-02","reactions":{}}