Polynomial time algorithm estimates antiferromagnetic Ising model partition function
On Zeros and Algorithms for Disordered Systems II: The Antiferromagnetic Ising Model up to Kesten-Stigum
Data Structures and Algorithms
Summary
The paper addresses how to accurately estimate a key number called the partition function in a complex model used to study things like magnetism on random networks. The authors created an efficient algorithm that works well up to a certain threshold, known as the Kesten-Stigum threshold, which is believed to be the best possible limit for such computations. They proved that certain problematic zeros, which could make the calculation hard, do not appear near this range, making the algorithm reliable. This work helps understand where efficient estimation is feasible in these complicated systems.
What this means in practice
- •For statistical physics modelers: Efficiently compute partition functions of antiferromagnetic models on random networks up to the Kesten-Stigum threshold.
- •For combinatorial optimization engineers: Design faster algorithms for counting and sampling solutions in complex network systems within the replica symmetric regime.
Authors
Ferenc Bencs, Brice Huang, Daniel Z. Lee, Kuikui Liu, Guus Regts
Abstract
We give the first polynomial-time algorithm to estimate the partition function of the antiferromagnetic Ising model on the uniformly random $d$-regular graph to arbitrarily high accuracy for all inverse temperatures up to the Kesten-Stigum threshold. This is the entire regime in which the model is "replica symmetric," and is conjectured to be optimal for polynomial-time counting and sampling. To achieve our algorithmic result, we establish the absence of Fisher zeros for the partition function in a constant-width strip around the interval from $0$ up to the Kesten-Stigum threshold, with high probability over the randomness of the input graph. AI Disclosure: The overarching vision and proof architecture were developed solely by the authors without AI input. GPT 5.5 Pro was used, with extensive guidance from the authors, for only a few minor technical aspects of the proof. The authors independently verified correctness and wrote everything by hand. We take full responsibility for its contents. A more detailed statement can be found in Section 1.2.