Critical window for approximate counting in dense Ising models
This work addresses a fundamental problem in theoretical computer science and statistical physics by providing precise hardness results for approximate counting at criticality, which is incremental but crucial for understanding computational limits.
The paper tackles the problem of approximating the partition function of dense Ising models in the critical regime, proving nearly tight hardness bounds within a window of width N^{-1/2+ε} for any constant ε>0, which establishes the first sharp scaling window for computational complexity.
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}$. 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+\varepsilon}$ for any constant $\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.