{"id":"arxiv/2610.40598","url":"https://arxiv.org/abs/2610.40598","tags":["cs.DS","cond-mat.dis-nn","math-ph","math.PR"],"score":0,"title":"On Zeros and Algorithms for Disordered Systems II: The Antiferromagnetic Ising Model up to Kesten-Stigum","domain":"cs.DS","source":"arxiv","authors":["Ferenc Bencs","Brice Huang","Daniel Z. Lee","Kuikui Liu","Guus Regts"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-29","reactions":{}}