Critical window for approximate counting in dense Ising models

Andreas Galanis, Daniel Štefankovič, Eric Vigoda · 2026

Read Critical window for approximate counting in dense Ising models by Andreas Galanis, Daniel Štefankovič, Eric Vigoda (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-21406.txt.

Introduction

Galanis and co-authors study how hard it is to approximate the partition function of dense Ising models near criticality. Recent work found fast mixing at criticality and slightly beyond it. They prove matching hardness bounds, giving a sharp window for this counting problem. They show approximation stays hard in a window only slightly wider than the fast-mixing window. Their proof aggregates fluctuations across all gadgets at once, rather than bounding each gadget alone.

Catalog record

CREATORAndreas Galanis, Daniel Štefankovič, Eric Vigoda
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31116
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.21406

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Critical window for approximate counting in dense Ising models Andreas Galanis, Daniel Štefankovič, Eric Vigoda Abstract We study the complexity of approximating the partition function of dense Ising models in the critical regime. Recent work of Chen, Chen, Yin, and Zhang (FOCS 2025) established fast mixing at criticality, and even beyond criticality in a window of width N − 1 / 2 N^{-1/2} . We complement these algorithmic results by proving nearly tight hardness bounds, thus yielding the first instance of a sharp scaling window for the computational complexity of approximate counting. Specifically, for the dense Ising model we show that approximating the partition function is computationally hard within a window of width N − 1 / 2 + ε N^{-1/2+\varepsilon} for any constant ε > 0 \varepsilon>0 . Standard hardness reductions for non-critical regimes break down at criticality due to bigger fluctuations in the underlying gadgets, leading to suboptimal bounds. We overcome this barrier via a global approach which aggregates fluctuations across all gadgets rather than requiring tight concentration guarantees for each individually. This new approach yields the optimal exponent for the critical window. † † footnotetext: For the purpose of Open Access, the authors have applied a CC BY public copyright licence to any Author Accepted Manuscript version arising from this submission. All data is provided in full in the results section of this paper. 1 Introduction Phase transitions are often accompanied by critical windows : narrow parameter regimes around a critical point in which the global behavior of the system changes rapidly as a function of the system size. The delicate behavior inside such windows has been a key challenge in probability and statistics, and has recently emerged as a new frontier in sampling and approximate counting. In this paper, we study critical windows for the Ising model, focusing on their implications for computational complexity. Given a symmetric interaction matrix J\in\mathbb{R}^{N\times N} , the Ising model is the probability distribution \mu_{J} defined by \mu_{J}(\sigma)\propto\exp\big(\tfrac{1}{2}\sigma^{\top}J\sigma\big)\mbox{ for all }\sigma\in\{\textup{{-}}1,\textup{{+}}1\}^{N} . We will refer to the entries of J as weights. The normalizing constant Z_{J}=\sum_{\sigma\in\{\textup{{+}}1,\textup{{-}}1\}^{N}}\exp\!\left(\frac{1}{2}\sigma^{\top}J\sigma\right) is called the partition function. Typically one takes J to be the adjacency matrix of a graph G scaled by some parameter, and in this case \mu_{J} can also be viewed as a weighted distribution on the cuts of the graph. One of the most well-studied cases is the N -vertex complete graph where each edge has weight \frac{\beta}{N} and \beta>0 is known as the inverse temperature. We will focus on the setting where J is positive semidefinite (psd) and its spectral norm is bounded by some constant, specifically when \left\|{J}\right\|_{2}\approx 1 which captures criticality for dense graphs. 1 1 1 Note that by adding to J a scalar multiple of the identity matrix, the Ising distribution does not change; so having J to be psd and \left\|{J}\right\|_{2}\approx 1 is equivalent to considering matrices J whose spectral diameter (the difference between the largest and smallest eigenvalues of J ) is roughly equal to 1. In the case of the complete graph, it is well-known that the model undergoes a phase transition as N grows large at the critical point \beta_{c}=1 . For a configuration \sigma\in\{\textup{{-}}1,\textup{{+}}1\}^{N} , let m_{\sigma}=\sum_{i\in[N]}\sigma_{i} be the so-called magnetization of \sigma . When \beta<\beta_{c} , entropy dominates and correlations are weak, so a typical sample \sigma\sim\mu_{J} is roughly balanced between \textup{{\textpm}}1 spins and satisfies |m_{\sigma}|=O(N^{1/2}) . For \beta>\beta_{c} , interactions dominate and long-range order emerges in the sense that a typical \sigma\sim\mu_{J} is biased towards either the “ + phase” or the “ - phase” where |m_{\sigma}|=\Theta(N) . So, away from criticality, the underlying system behaves predictably. Around criticality however, for \beta=1\pm O(\tfrac{1}{N^{1/2}}) , the above high and low temperatures principles no longer apply cleanly; instead they lead to a conflating behaviour which exhibits nontrivial scaling: a typical sample \sigma\sim\mu_{J} has still a somewhat balanced number of \textup{{\textpm}}1 but |m_{\sigma}|=O(N^{3/4}) , i.e., the fluctuations of the spins are of order N^{3/4} . Understanding critical-window regimes has been a key challenge in approximate counting/sampling, where there is a vast amount of results for non-critical cases but only few that apply to criticality, especially for more general classes of graphs. In terms of Markov chains, it has been shown on the complete graph [ 18 , 10 ] that the standard Glauber dynamics has mixing time O(N\log N) for \beta<1 , O(N^{3/2}) for \beta=1 , and \mathrm{e}^{\Omega(N)} for \beta>1 , see also [ 19 , 9 , 14 , 5 , 4 , 6 , 16 ] for related results. Similar flavored but more delicate-to-prove Markov-chain results have also been developed in the 2D lattice [ 21 , 20 , 15 ] . From an algorithmic/complexity viewpoint, progress for the case of a general interaction matrix J has only been made very recently, using spectral independence theory [ 3 ] . In particular, for the case of the Ising model with general interaction matrix J , [ 2 , 12 ] showed that the Glauber dynamics mixes rapidly when \left\|{J}\right\|_{2}<1 , whereas [ 13 , 17 ] showed hardness of approximately sampling/counting when \left\|{J}\right\|_{2}>1 . Note that the condition \left\|{J}\right\|_{2}=1 translates precisely to the critical value \beta_{c}=1 for the complete graph. An analogous line of techniques has been developed for sparse Ising models (e.g. on graphs of bounded degree d ), where the qualitative picture is analogous but the relevant phase transitions are more closely related to regular trees and random regular graphs. Despite these developments for non-critical regimes, understanding the complexity at criticality appeared to still be elusive. Recent work of Chen, Chen, Yin and Zhang [ 7 ] however made a major leap forward, showing fast mixing for the Glauber dynamics when \|J\|_{2}=1 , and showed similar results for the Ising and hard-core model in sparse graphs. For the dense setting in particular that we consider here, they managed to go even beyond criticality and showed that, for any fixed constant \alpha>0 , the mixing time is O(N^{3/2}\log{N}) when \|J\|_{2}\leq 1+\frac{\alpha}{N^{1/2}} . We prove a nearly-matching hardness result, thereby establishing the first example of a sharp scaling window for the computational complexity of the approximation problem. Theorem 1 . Fix any arbitrarily small constant \varepsilon>0 . It is NP-hard to approximate the Ising partition function on N\times N psd matrices J when \|J\|_{2}\leq 1+\frac{1}{N^{1/2-\varepsilon}} , even within a factor \exp(N^{c}) where c=c(\varepsilon)>0 is a constant depending only on \varepsilon . We remark that away from criticality it is sometimes possible to obtain hardness of approximation within a factor of \exp(\Omega(N)) . This is not the case for the critical case we are considering here: for any \eta>0 and \|J\|_{2}=1+\eta , setting \hat{J}=\tfrac{1}{1+\eta}J yields that \|\hat{J}\|_{2}=1 and Z_{J}/Z_{\hat{J}}=\exp(\Theta(N\eta)) . One can then obtain in poly-time an approximation to Z_{\hat{J}} , and therefore Z_{J} , using the critical-case algorithm of [ 7 ] . For \eta=\tfrac{1}{N^{1/2-\varepsilon}} , this yields in particular an \exp(\Theta(N^{1/2+\varepsilon})) -factor approximation to Z_{J} , even for matrices J with \|J\|_{2}=1+\frac{1}{N^{1/2-\varepsilon}} that fall into the scope of Theorem 1 . For the sparse Ising and hard-core models, Chen, Chen, Yin and Zhang [ 7 ] (see also [ 8 ] ) establish polynomial mixing of the Glauber dynamics at criticality for

Read the complete text