On Zeros and Algorithms for Disordered Systems II: The Antiferromagnetic Ising Model up to Kesten-Stigum
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.
Related
- Bethe Hessian Recovery through the Kesten-Stigum Regime
- The Value of Depth in Message Passing on Sparse Graphs: A Kesten-Stigum Dichotomy
- Slow Beats Fast at the Kesten-Stigum Threshold: Minimax, Fisher-Information and Belief-Propagation Characterizations of the Information-Computation Gap in Sparse Stochastic Block Models
- The oriented Kesten--McKay law for random regular digraphs
- Performance Evaluation of Metaheuristic Algorithms for Fractional-Order PID Controller Tuning in Non-Linear Systems
BibTeX
@misc{bencs2026zeros,
title = {{On Zeros and Algorithms for Disordered Systems II: The Antiferromagnetic Ising Model up to Kesten-Stigum}},
author = {Ferenc Bencs and Brice Huang and Daniel Z. Lee and Kuikui Liu and Guus Regts},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.40598},
eprint = {2610.40598},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.40598},
}
RIS
TY - UNPB
TI - On Zeros and Algorithms for Disordered Systems II: The Antiferromagnetic Ising Model up to Kesten-Stigum
AU - Ferenc Bencs
AU - Brice Huang
AU - Daniel Z. Lee
AU - Kuikui Liu
AU - Guus Regts
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.40598
UR - https://arxiv.org/abs/2610.40598
AB - 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.
ER -