← 研踪 PaperTrailarXiv:2610.40598 · v1
On Zeros and Algorithms for Disordered Systems II: The Antiferromagnetic Ising Model up to Kesten-Stigum
首次提交 2026-10-30 01:50
版本更新 2026-10-30 01:50
雷达观测 2026-10-30 13:28
摘要
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.
作者备注：98 pages
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-10-30 01:50 · 最新观测版本
On Zeros and Algorithms for Disordered Systems II: The Antiferromagnetic Ising Model up to 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.
查看此版本解读 →查看此版本原文 ↗