On Zeros and Algorithms for Disordered Systems II: The Antiferromagnetic Ising Model up to Kesten-Stigum
Authors: Ferenc Bencs, Brice Huang, Daniel Z. Lee, Kuikui Liu, Guus Regts
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.
The papers around it, by date and closeness
Higher is closer to this paper; left is older. Lines join papers close to each other: groups of lines are sub-topics. Select a point to see why it is there. Back to the summary of this paper
Papers around this one
Ranked by how close their title and abstract are to this paper’s. Select some to read them together.
Closest papers
-
Computational thresholds for the fixed-magnetization Ising modelCharles 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…
-
Approximation algorithms for the random-field Ising modelTyler 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…
-
Efficient Algorithms for Approximating Quantum Partition FunctionsRyan 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.
-
Sampling from the Potts model at low temperatures via Swendsen–Wang dynamicsAntonio 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…
-
On the tractability of sampling from the Potts model at low temperatures via random-cluster dynamicsAntonio 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…
-
The complexity of approximating the complex-valued Ising model on bounded degree graphsAndreas 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…
-
Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphsTyler 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…
-
Exact Fractional Inference via Re-Parametrization & Interpolation between Tree-Re-Weighted- and Belief Propagation- AlgorithmsHamidreza 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.