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 summary · arXiv: 2610.40598v1 · cs.DS

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

Original paper Submitted to arXiv on 29 Oct. 2026 98 pages License: NONEXCLUSIVE-DISTRIB 1.0 Also in: fr

How to read this summary? Illustrated guide

The essentials

The paper proves zero-freeness and deterministic polynomial-time partition-function approximation for the antiferromagnetic Ising model on random regular graphs at every fixed inverse temperature below Kesten–Stigum.

Question

Can the partition function of the antiferromagnetic Ising model on uniformly random regular graphs be approximated to arbitrarily high accuracy throughout the replica-symmetric regime? The paper also asks whether Fisher zeros remain away from the corresponding real inverse-temperature interval.

Method

The authors analyze uniformly random d-regular graphs for fixed d ≥ 3 through the configuration model, combining Jensen’s formula, complex moment estimates, cycle-based analytic reweighting, and truncation of atypical contributions. For any fixed 0 < δ < 1 and inverse temperature between 0 and (1 − δ) times the Kesten–Stigum threshold, they prove a constant-width zero-free strip with probability 1 − o(1). Barvinok interpolation then uses O(log(n/ε)) Taylor terms to obtain multiplicative error between exp(−ε) and exp(ε) in time (n/ε)^C, where C depends on d and δ.

Findings

Result A deterministic polynomial-time algorithm approximates the partition function to arbitrarily high accuracy with high probability over the random graph, for every fixed inverse temperature strictly below Kesten–Stigum.
See the passage in the paper
In this paper, we make progress on the high-temperature (small $\beta$) side of the aforementioned conjecture by giving the first polynomial-time approximate counting algorithm for all $\beta$ up to $\beta_{\mathsf{KS}}(d)$.
Result With high probability, the partition function has no Fisher zeros in a constant-width complex neighborhood of any real interval ending a fixed distance below Kesten–Stigum.
See the passage in the paper
The key to guaranteeing correctness of our algorithm is the absence of zeros in a constant-width strip around the interval $[0,(1-\delta)\cdot\beta_{\mathsf{KS}}(d)]$ for any $\delta>0$.
Result The interpolation algorithm obtains the required multiplicative accuracy by retaining only logarithmically many Taylor terms.
See the passage in the paper
To approximate $$q_{G}(p(1))=\tfrac{1}{2^{|V|}}Z_{G}(\beta)$$ up to a multiplicative factor $e^{\varepsilon}$, it suffices to truncate the Taylor series of $\log(q_{G}(p(z)))$ after $O(\log(n/\varepsilon))$ terms (see [5, Lemma 2.2.1]).

Limitations

The counting algorithm does not directly provide an approximate sampling algorithm because the model without an external field is not self-reducible.
See the passage in the paper
Our approximate counting algorithm does not immediately imply an approximate sampling algorithm for the Gibbs measure $\mu_{G,\beta}$. This is because we only work with the antiferromagnetic Ising model without external field, which is not self-reducible in the sense of [30].
The authors do not know how to efficiently certify the approximation guarantee on a given input graph.
See the passage in the paper
Unfortunately, we do not know how to show that our algorithm is certifiable in this sense. In particular, we do not know how to certify the requisite zero-freeness of $Z_{G}(\beta)$ given $G$.
The theorems require a fixed positive gap below Kesten–Stigum and do not establish the endpoint itself.

Why it matters

The result extends high-accuracy average-case approximate counting to every fixed inverse temperature below the replica-symmetry-breaking threshold, beyond the range reached by the prior sampling methods discussed in the paper. It establishes the counting and zero-freeness sides of the proposed coincidence of average-case phase transitions, without resolving sampling or rapid mixing throughout that regime.

Written by AI from the paper. Passages are checked word for word against the text we analysed; the rest may contain errors.

AI-generated keywords: Antiferromagnetic Ising model; Random regular graphs; Approximate counting; Kesten–Stigum threshold; Complex zero-freeness

Read further

Comprehensive Summary
Layman's Summary
Blog article
Original abstract

This paper investigates how accurately and efficiently the partition function of the antiferromagnetic Ising model can be computed on a uniformly random d-regular graph. The model assigns a spin of +1 or −1 to each vertex and gives each configuration weight exp(βH), where H counts the edges joining opposite spins. For nonnegative inverse temperature β, configurations that cut more edges receive greater weight. The partition function is the sum of these weights over all configurations. The authors ask whether polynomial-time approximation is possible throughout the high-temperature regime below the Kesten–Stigum threshold, substantially beyond the threshold governing algorithms on arbitrary bounded-degree graphs. Their main result is a deterministic approximate-counting algorithm for every fixed degree d ≥ 3 and every fixed positive gap δ below the Kesten–Stigum threshold, βKS(d) = 2 arctanh(1/√(d−1)), which is approximately 2/√d for large d. For any β between zero and (1−δ)βKS(d), the algorithm estimates the partition function within multiplicative factors exp(−ε) and exp(ε), in time (n/ε)^C, where C depends on d and δ. The guarantee holds with probability 1−o(1) as the number of vertices n grows. The algorithm itself is deterministic; the probability refers solely to the randomly chosen input graph. The theorem covers every fixed temperature strictly below the threshold, but not the threshold itself. The central technical achievement is a complex-analytic zero-free region. With high probability, the partition function has no Fisher zeros in a constant-width complex neighborhood of the interval from zero to (1−δ)βKS(d). This width depends on d and δ, but not on n. The result enables Barvinok’s interpolation method: following a suitable change of variables and analytic mapping, the algorithm approximates the logarithm of the partition function using only O(log(n/ε)) Taylor coefficients. Bounded-degree induced-subgraph counting techniques allow these coefficients to be computed in polynomial time. The proof of zero-freeness overcomes two obstacles to a straightforward second-moment argument. First, short cycles produce persistent multiplicative fluctuations in the partition function. To address them, the authors construct an analytic reweighting factor, inspired by small subgraph conditioning, that approximately cancels these cycle-driven fluctuations. Second, the untruncated normalized second moment becomes exponentially large beyond β2nd(d) = log((√d+1)/(√d−1)), a threshold strictly below βKS(d). This growth is caused by rare graphs with exceptionally large partition functions. The proof therefore truncates contributions according to whether two independent Gibbs configurations have overlap close to zero. A major ingredient strengthens earlier overlap estimates to exponential accuracy. Using planted inference models, Gaussian side information, free-energy concentration, and tree-broadcasting arguments, the authors show that problematic overlap contributions constitute only an exponentially small fraction of the relevant moments. They also derive precise complex first-moment and truncated second-moment estimates through contour integration, steepest descent, and Poisson summation. Jensen’s formula then converts these estimates into a bound showing that the expected number of nearby zeros tends to zero. The results support the conjectured connection between replica symmetry, zero-freeness, and efficient counting on random regular graphs. They do not, however, establish computational hardness above the Kesten–Stigum threshold, rapid mixing throughout the newly covered regime, or an approximate-sampling algorithm. The counting guarantee is average-case rather than valid for every regular graph, and the authors do not know how to certify correctness efficiently on a particular input. The runtime bounds also depend on the fixed distance below the threshold.

Counting Spin Configurations up to the Kesten–Stigum Threshold

A system can be easy to describe yet surprisingly difficult to count. Put a spin of +1 or −1 on each vertex of a graph, reward neighboring spins that disagree, and add up the weights of every possible configuration. This sum, called the partition function, captures the statistical behavior of the antiferromagnetic Ising model. But with 2ⁿ configurations on n vertices, direct calculation quickly becomes impractical.

In “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, and Guus Regts show how to approximate this sum efficiently on typical random regular graphs throughout a substantially expanded temperature regime. Their key tool is an unexpected bridge between counting algorithms and zeros of functions in the complex plane.

The Model and the Counting Challenge

The graphs in question are uniformly random d-regular graphs: every vertex has exactly d neighbors, and the graph is chosen uniformly from the possibilities. Each spin configuration receives weight exp(βH), where H counts edges whose endpoints have opposite spins. The nonnegative parameter β is the inverse temperature. Larger β puts greater emphasis on configurations that cut many edges.

The partition function adds these weights over all configurations. Approximating it efficiently means avoiding an exhaustive search while retaining a rigorous accuracy guarantee. Algorithms for arbitrary bounded-degree graphs face a more restrictive temperature threshold. The authors ask whether the typical structure of a random regular graph permits efficient counting much further.

What the Main Theorem Delivers

The answer is yes, up to any fixed distance below the Kesten–Stigum threshold. For degree d, this threshold is βKS(d) = 2 arctanh(1/√(d−1)), approximately 2/√d when d is large.

For every fixed d ≥ 3 and every fixed positive gap δ, the authors provide a deterministic algorithm valid for 0 ≤ β ≤ (1−δ)βKS(d). Its main guarantees are:

The estimate lies between exp(−ε) and exp(ε) times the true partition function.
The running time is (n/ε)ᶜ, where C depends on d and δ.
The guarantee holds with probability tending to one as the number of vertices grows.

Importantly, the algorithm itself uses no randomness. The probability refers entirely to the random input graph. The theorem covers every fixed temperature strictly below the threshold, but does not include the threshold itself.

Why Complex Zeros Matter

The central technical result concerns Fisher zeros: zeros of the partition function when inverse temperature is allowed to take complex values. Although physical temperatures are real, these complex zeros control whether analytic approximation methods can work reliably.

The authors prove that, with high probability, there are no such zeros in a constant-width complex neighborhood of the entire interval from zero to (1−δ)βKS(d). That width may depend on d and δ, but it does not shrink as the graph grows.

This zero-free neighborhood makes an interpolation approach possible. After a suitable change of variables and analytic mapping, the algorithm approximates the logarithm of the partition function using only O(log(n/ε)) Taylor coefficients. Techniques for counting bounded-size induced subgraphs in bounded-degree graphs make those coefficients computable in polynomial time. Complex analysis thus supplies the foundation for a concrete counting algorithm.

Two Obstacles Behind the Proof

Short cycles create lasting fluctuations

Random regular graphs have tree-like local structure, but they also contain short cycles. These cycles cause persistent multiplicative fluctuations in the partition function, obstructing a straightforward second-moment argument. The authors construct an analytic reweighting factor, inspired by small subgraph conditioning, that approximately cancels these cycle-driven effects.

Rare graphs distort the second moment

A second obstacle appears before the Kesten–Stigum threshold. The ordinary normalized second moment becomes exponentially large beyond β2nd(d) = log((√d+1)/(√d−1)). This reflects the influence of rare graphs with exceptionally large partition functions, rather than typical behavior alone.

To control that distortion, the proof truncates contributions according to whether two independent Gibbs configurations have overlap close to zero. Roughly, overlap measures how strongly two spin assignments align. The authors strengthen earlier overlap estimates to exponential accuracy, showing that problematic contributions form only an exponentially small fraction of the relevant moments.

This step draws on planted inference models, Gaussian side information, free-energy concentration, and tree-broadcasting arguments. Precise complex moment estimates then come from contour integration, steepest descent, and Poisson summation. Finally, Jensen’s formula turns those estimates into a bound showing that the expected number of nearby zeros tends to zero.

A Stronger Counting Result, with Clear Limits

The work supports a proposed connection between replica symmetry, complex zero-freeness, and efficient counting in disordered systems. It shows that typical random regular graphs admit rigorous approximation guarantees well beyond those available for arbitrary bounded-degree inputs.

Its limits are equally important. The result does not prove computational hardness above Kesten–Stigum, rapid mixing throughout the expanded regime, or an approximate-sampling algorithm. Nor does it provide an efficient certificate of correctness for a particular graph. The guarantee remains average-case, and the runtime depends on the fixed distance below the threshold. Within those boundaries, it establishes a substantial advance: complex zeros can reveal where efficient counting remains possible.

Created on 02 Nov. 2026

Was this synthesis useful?

Score: 0

Ask questions about this paper to our AI assistant

How to chat with this paper? Illustrated guide

Compare with the PDF

You can also chat with multiple papers at once here.

AI assistant instructions?

Tools for this paper

Explain it differently 3 free rewrites left today

Save to a collection Group papers in collections to compare them, chat with them and export them. Create a free account Log in

Export BibTeX · RIS (Zotero, Mendeley, EndNote) · Obsidian (Markdown) · Notion (Markdown)

Advanced tools Premium

For researchers who follow a field closely: citation alerts, journal-club slides, version comparison and Zotero export. Discover Premium

Zotero

Citation alerts Citation alerts guide

Who works on it? The people and institutions who publish on its topic

Weekly letter Presented in "Computing beyond AI this week" of 2 November 2026. Computing beyond AI this week: Better algorithms, smaller machines, harder tests

Journal club Premium+ Slides to present it Propose for the journal club

Versions What changed between versions

Talk about it in public Premium+ Press kit: release, questions, hype check Press kit guide

Papers around this one

See them on a map

Ranked by how close their title and abstract are to this paper’s. Select some to read them together.

Closest papers

Very close Broader context
Computational thresholds for the fixed-magnetization Ising model
Charles Carlson, Ewan Davies, Alexandra Kolla et al. · 2021 · Symposium on the Theory of Computing · cited 14 times · Not summarized yet

Computational thresholds for fixed-magnetization ferromagnetic Ising counting and sampling on bounded-degree graphs, rather than antiferromagnetic Ising on random regular graphs.

Abstract
The ferromagnetic Ising model is a model of a magnetic material and a central topic in statistical physics. It also plays a starring role in the algorithmic study of approximate counting: approximating the partition function of the ferromagnetic Ising model with uniform external field is tractable at all temperatures and on all graphs, due to the randomized algorithm of Jerrum and Sinclair. Here we show that hidden inside the model are hard computational problems. For the class of bounded-degree graphs we find computational thresholds for the approximate counting and sampling problems for the ferromagnetic Ising model at fixed magnetization (that is, fixing the number of +1 and −1 spins). In…
Close Broader context
Approximation algorithms for the random-field Ising model
Tyler Helmuth, Holden Lee, Will Perkins et al. · 2021 · SIAM Journal on Discrete Mathematics · cited 3 times · Not summarized yet

Approximation algorithms for ferromagnetic Ising partition functions with random external fields, whereas this paper studies antiferromagnetic interactions on random regular graphs.

Abstract
Approximating the partition function of the ferromagnetic Ising model with general external fields is known to be #BIS-hard in the worst case, even for bounded-degree graphs, and it is widely believed that no polynomial-time approximation scheme exists. This motivates an average-case question: are there classes of instances for which polynomial-time approximation schemes exist? We investigate this question for the random field Ising model on graphs with maximum degree $\Delta$. We establish the existence of fully polynomial-time approximation schemes and samplers with high probability over the random fields if the external fields are IID Gaussians with variance larger than a constant dependi…
Close Another approach to the problem
Efficient Algorithms for Approximating Quantum Partition Functions
Ryan L. Mann, Tyler Helmuth · 2020 · Journal of Mathematics and Physics · cited 30 times · Not summarized yet

Efficient Algorithms for Approximating Quantum Partition Functions uses a quantum cluster expansion for high-temperature approximation, rather than zero-free strips and interpolation.

Abstract
We establish a polynomial-time approximation algorithm for partition functions of quantum spin models at high temperature. Our algorithm is based on the quantum cluster expansion of Netocny and Redig and the cluster expansion approach to designing algorithms due to Helmuth, Perkins, and Regts. Similar results have previously been obtained by related methods, and our main contribution is a simple and slightly sharper analysis for the case of pairwise interactions on bounded-degree graphs.
Close Broader context
Sampling from the Potts model at low temperatures via Swendsen–Wang dynamics
Antonio Blanca, Reza Gheissari · 2023 · IEEE Annual Symposium on Foundations of Computer Science · cited 7 times · Not summarized yet

Sampling from the Potts model at low temperatures studies Swendsen–Wang sampling on graph families, not partition-function approximation for antiferromagnetic Ising.

Abstract
Sampling from the q-state ferromagnetic Potts model is a fundamental question in statistical physics, probability theory, and theoretical computer science. On general graphs, this problem is computationally hard, and this hardness holds at arbitrarily low temperatures. At the same time, in recent years, there has been significant progress showing the existence of low-temperature sampling algorithms in various specific families of graphs. Our aim in this paper is to understand the minimal structural properties of general graphs that enable polynomial-time sampling from the q-state ferromagnetic Potts model at low temperatures. We study this problem from the perspective of the widely-used Swen…
Close Broader context
On the tractability of sampling from the Potts model at low temperatures via random-cluster dynamics
Antonio Blanca, Reza Gheissari · 2023 · Probability theory and related fields · cited 5 times · Not summarized yet

On the tractability of sampling from the Potts model at low temperatures studies random-cluster sampling, rather than Ising partition-function approximation.

Abstract
Sampling from the q-state ferromagnetic Potts model is a fundamental question in statistical physics, probability theory, and theoretical computer science. On general graphs, this problem may be computationally hard, and this hardness holds at arbitrarily low temperatures. At the same time, in recent years, there has been significant progress showing the existence of low-temperature sampling algorithms in various specific families of graphs. Our aim in this paper is to understand the minimal structural properties of general graphs that enable polynomial-time sampling from the q-state ferromagnetic Potts model at low temperatures. We study this problem from the perspective of random-cluster d…
Close Same question
The complexity of approximating the complex-valued Ising model on bounded degree graphs
Andreas Galanis, L. Goldberg, Andrés Herrera-Poyatos · 2021 · SIAM Journal on Discrete Mathematics · cited 10 times · Not summarized yet

The complexity of approximating the complex-valued Ising model studies partition-function approximation with complex interactions on bounded-degree graphs.

Abstract
We study the complexity of approximating the partition function $Z_{\mathrm{Ising}}(G; \beta)$ of the Ising model in terms of the relation between the edge interaction $\beta$ and a parameter $\Delta$ which is an upper bound on the maximum degree of the input graph $G$. Following recent trends in both statistical physics and algorithmic research, we allow the edge interaction $\beta$ to be any complex number. Many recent partition function results focus on complex parameters, both because of physical relevance and because of the key role of the complex case in delineating the tractability/intractability phase transition of the approximation problem. In this work we establish both new tractab…
Close Same method, another problem
Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs
Tyler Helmuth, Matthew Jenssen, Will Perkins · 2020 · Annales De L Institut Henri Poincare-probabilites Et Statistiques · cited 34 times · Not summarized yet

Finite-size scaling for the random-cluster model uses polymer models and cluster expansions to obtain algorithms on random regular graphs.

Abstract
For $\Delta \ge 5$ and $q$ large as a function of $\Delta$, we give a detailed picture of the phase transition of the random cluster model on random $\Delta$-regular graphs. In particular, we determine the limiting distribution of the weights of the ordered and disordered phases at criticality and prove exponential decay of correlations away from criticality. Our techniques are based on using polymer models and the cluster expansion to control deviations from the ordered and disordered ground states. These techniques also yield efficient approximate counting and sampling algorithms for the Potts and random cluster models on random $\Delta$-regular graphs at all temperatures when $q$ is large…
Close Broader context
Exact Fractional Inference via Re-Parametrization & Interpolation between Tree-Re-Weighted- and Belief Propagation- Algorithms
Hamidreza Behjoo, M. Chertkov · 2023 · Trans. Mach. Learn. Res. · cited 1 time · Not summarized yet

Exact Fractional Inference develops variational approximations to Ising partition functions, unlike the paper’s rigorous randomized-graph approximation algorithm.

Abstract
Computing the partition function, $Z$, of an Ising model over a graph of $N$ \enquote{spins} is most likely exponential in $N$. Efficient variational methods, such as Belief Propagation (BP) and Tree Re-Weighted (TRW) algorithms, compute $Z$ approximately by minimizing the respective (BP- or TRW-) free energy. We generalize the variational scheme by building a $\lambda$-fractional interpolation, $Z^{(\lambda)}$, where $\lambda=0$ and $\lambda=1$ correspond to TRW- and BP-approximations, respectively. This fractional scheme -- coined Fractional Belief Propagation (FBP) -- guarantees that in the attractive (ferromagnetic) case $Z^{(TRW)} \geq Z^{(\lambda)} \geq Z^{(BP)}$, and there exists a un…

Go further

How are these papers found?

We compare the title and abstract of this paper with those of every paper summarized on this site, and with the papers Semantic Scholar recommends, those it cites and those citing it (for a much-cited paper, its most recent citations and, from OpenAlex, the most cited ones). Among the prior work and the follow-ups, the papers that use each other in depth, a method it uses and the much-cited follow-ups come a little higher. The levels (very close, close, related) come from the similarity of the texts, not from a judgment of quality; * marks a paper without an abstract, compared by its title. The sentence under a paper is written by an AI from the two abstracts: check it in the papers. A paper marked not relevant by three readers leaves the list.

Updated on 2 November 2026.

Disclaimer: The AI-based summarization tool and virtual assistant provided on this website may not always provide accurate and complete summaries or responses. We encourage you to carefully review and evaluate the generated content to ensure its quality and relevance to your needs.

On Zeros and Algorithms for Disordered Systems II: The Antiferromagnetic Ising Model up to Kesten-Stigum

The essentials

Question

Method

Findings

Limitations

Why it matters

Read further

Definitions

Counting Spin Configurations up to the Kesten–Stigum Threshold

The Model and the Counting Challenge

What the Main Theorem Delivers

Why Complex Zeros Matter

Two Obstacles Behind the Proof

Short cycles create lasting fluctuations

Rare graphs distort the second moment

A Stronger Counting Result, with Clear Limits

Ask questions about this paper to our AI assistant

Tools for this paper

Advanced tools Premium

Papers around this one

Closest papers

Go further

Cite this paper (BibTeX)