论无序系统的零点与算法 II：至 Kesten-Stigum 阈值的反铁磁 Ising 模型
On Zeros and Algorithms for Disordered Systems II: The Antiferromagnetic Ising Model up to Kesten-Stigum
Ferenc Bencs, Brice Huang, Daniel Z. Lee, Kuikui Liu, Guus Regts
AI 速览：作者提出首个在均匀随机 d-正则图上、对反铁磁 Ising 模型在直至 Kesten-Stigum 阈值的全部逆温度范围内以任意高精度估计配分函数的多项式时间算法。
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.