CS Paper Radar

An FPRAS for Antiferromagnetic Ising Models on Random Regular Bipartite Graphs

Zhidan Li, Kuan Yang

cs.DS math.PR ·submitted 2026-08-19 06:54 UTC · v1

Abstract

We design randomized approximation schemes for the partition function of antiferromagnetic Ising models with uniform external field on random regular bipartite graphs. Our algorithm generalizes the approach of Kocurek, Oveis Gharan and Tjowasi (arXiv, 2026) for hard-core models on the same random graph model beyond the uniqueness threshold. We show that, as long as $λ$ is upper bounded by a constant and $λ(1 - β) \lesssim Δ^{-1/2}$, an efficient randomized algorithm approximates the partition function with high probability. The algorithm first truncates configurations that are large on either side of the bipartition and then samples from Gibbs distributions conditioned on fixed sizes on one or both sides. To choose an optimal truncation bound, we establish concentration properties of the Gibbs distribution on random regular bipartite graphs. Then we apply high-dimensional expansion and prove trickle-down theorems to obtain fast samplers for the conditioned distributions.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.DS cond-mat.dis-nnmath-phmath.PR ·2026-10-29 ·Ferenc Bencs, Brice Huang, Daniel Z. Lee, Kuikui Liu, Guus Regts
similarity 0.72
Abstract · 98 pages

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.

0.26

Deterministic Approximation of the Total Variation Distance Between Spin Systems

cs.DS ·2026-10-08 ·Zelin Li, Minji Yang
similarity 0.70
Abstract

We study deterministic relative approximation of the total variation distance between two Gibbs distributions induced by spin systems on the same bounded-degree graph. For the hard-core model, we give a deterministic polynomial-time $\varepsilon$-relative-error approximation when both external-field vectors lie in $[b,(1-η)λ_{\mathrm c}(Δ)]^V$, where $b>0$ and $η\in(0,1)$ are fixed and $λ_{\mathrm c}(Δ)$ is the hard-core uniqueness threshold. For the Ising model, we obtain deterministic polynomial-time algorithms in two settings: the ferromagnetic Lee--Yang regime and the antiferromagnetic correlation-decay regime. We develop a new deterministic framework that reduces this task to estimating suitably chosen partition functions.

0.23

The C-3PO Framework: Algorithms for $\#\mathrm{BIS}$-Hard Problems on Graphs with Low Threshold Rank or High Girth

cs.DS cs.DM ·2026-10-30 ·Ijay Narang
similarity 0.69
Abstract

We give approximate counting and sampling algorithms for spin models on graphs of low threshold rank or high girth. Given any $n$-vertex graph $G$, let $k_η= k_η(G)$ count normalized-Laplacian eigenvalues strictly below $η$. For $\varepsilon > 0$, an $\varepsilon$-approximate counting algorithm outputs an estimate $\widehat Z$ of the partition function $Z$ satisfying $(1-\varepsilon)Z\le\widehat Z\le(1+\varepsilon)Z$ with probability at least $3/4$. An $\varepsilon$-approximate sampling algorithm outputs a configuration whose distribution is within total variation distance $\varepsilon$ of the target distribution. We give the following results: (a) Ferromagnetic Potts. Fix $q\ge2$ and $η\in(0,1]$. There exists $β_0(q,η)$ such that, for every inverse temperature $β\geβ_0$, the zero-field $q$-state Potts model admits approximate counting and sampling algorithms: (i) On arbitrary graphs in time $\exp(O(k_η))\operatorname{poly}(n,1/\varepsilon).$ (ii) Fix $Δ\ge 3$. On $Δ$-regular graphs of girth $g$ in time $\exp(O(n e^{-g})) \operatorname{poly}(n,1/\varepsilon).$ (b) Bipartite hard-core. Fix $Δ\ge3$ and $η\in(0,1]$. There exists $λ_0(Δ,η)$ such that, for every fugacity $λ\geλ_0$, the hard-core model admits approximate counting and sampling: (i) On $Δ$-regular vertex-transitive bipartite graphs in time $\exp(O (k_η))\operatorname{poly}(n,1/\varepsilon).$ (ii) On $Δ$-regular bipartite graphs of girth $g$ in $\exp(O(n e^{- g}))\operatorname{poly}(n,1/\varepsilon).$ All four results follow from verifying the hypotheses of a new framework we call C-3PO. At a high level, the C-3PO algorithm proceeds by enumerating small cuts and reconstructing the original measure through cluster expansions. Underlying the algorithm is an improvement of subspace enumeration methods via active regression.

0.29

Zero-freeness for Random Regular Graphs up to the Replica Symmetry Breaking Threshold

cs.DS math-phmath.PR ·2026-10-29 ·Zejia Chen, Chunyang Wang, Xinyuan Zhang
similarity 0.65
Abstract · Revised and expanded: strengthened the characterization of the replica-symmetric phase, reorganized and expanded the proofs. 84 pages

We study antiferromagnetic spin systems on random regular graphs through the lens of the phase transitions characterized by the complex zeros of the partition function. Our motivating examples include the hardcore model and the antiferromagnetic Potts model (including proper $q$-colorings at $β=0$). For both models on random $d$-regular graphs, we establish, with high probability over the graph, zero-free regions throughout the interior of the replica-symmetric regime. Asymptotically, this regime extends up to tree occupation density $$α< α_{\mathrm{RSB}}(d) = (2\log d - 2\log\log d + 2 - 2\log 2 + o_d(1))/d$$ for the hardcore model and up to degree $$d < d_{\mathrm{RSB}}(q) = (2q-1)\log q - 2\log 2 + o_q(1)$$ for proper $q$-colorings. Leveraging the standard algorithmic implications of zero-freeness, we obtain deterministic polynomial-time algorithms that multiplicatively approximate the corresponding partition functions at fixed rational parameters throughout this regime, with high probability over the graph. Our algorithmic guarantees significantly improve upon prior work and extend beyond the parameter ranges reached by previously known search algorithms. As a key intermediate step, we establish the pointwise equivalence, away from the threshold, of three notions of replica symmetry: geometric (averaged pairwise correlation decay), thermodynamic (convergence to the Bethe free-energy prediction), and variational (nonpositivity of the Bethe functional). To establish zero-freeness, we develop reinforced small subgraph conditioning, lifting classical small subgraph conditioning to random holomorphic functions to control short-cycle fluctuations. We also use variational replica symmetry to obtain exponential planted overlap concentration. This enables a typical-graph truncation that controls complex second moments up to the replica symmetry breaking threshold.

0.28

Fast Algorithms for Stoquastic Spin Systems

cs.CC quant-phcs.DSmath.CO ·2026-08-19 ·Ryan L. Mann
similarity 0.64
Abstract · 30 pages, 0 figures

We establish a general framework for developing fast sampling and counting algorithms for stoquastic spin systems at high temperature. Our framework is based on a rapidly mixing Markov chain for polymer models and a subcritical percolation process for sampling individual polymers. We apply our framework to obtain fast algorithms for approximating the partition function and sampling from the thermal distribution of (1) general stoquastic spin systems, (2) ferromagnetic Heisenberg models, and (3) antiferromagnetic Heisenberg models on bipartite graphs. For the Heisenberg models, we obtain an improved bound on the inverse temperature by using their respective cycle and loop representations.

0.44

Approximating #BIS in $\exp(\widetilde O(n^{1/3}))$ Time

cs.DS ·2026-11-04 ·Jingcheng Liu, Yitong Yin
similarity 0.63
Abstract

We give randomized algorithms for approximately counting and nearly uniformly sampling independent sets in arbitrary bipartite graphs (#BIS). At fixed accuracy, both algorithms run in $\exp(O(n^{1/3}\log^{4/3}n))$ time on $n$-vertex graphs. More generally, the same running-time dependence on the number of variables holds for approximate counting and sampling with efficiently evaluable positive log-supermodular weights on Boolean variables. A weighted Sinclair-Jerrum walk on the self-reduction tree reduces these tasks to coarse lower estimates of residual log-partition functions. We obtain these estimates by optimizing a concave relaxation of an exact variational principle on the tree; threshold smoothing certifies that the low-degree search suffices.

0.29

An $\widetilde{O}\left(n^2 \right)$-Time Sampler for Zero-Field Ferromagnetic Ising Models

cs.DS math.PR ·2026-08-13 ·Weiming Feng, Heng Guo, Yiyao Zhang
similarity 0.61
Abstract · 17 pages

We give an approximate sampler for ferromagnetic Ising models with no field on arbitrary graphs that runs in time $\widetilde O(m+n)+\widetilde O_β(n^2\log^2 (1 / \varepsilon))$, where $n$ and $m$ are the numbers of vertices and edges, respectively, and $\varepsilon$ is the approximation error. Our approach combines Benczúr--Karger cut sparsification with a new mixing time analysis of the Glauber dynamics for the random-cluster model. The mixing time analysis features a new monotone edge-count Poincaré inequality.

0.10

Improved rapid phase ordering for Ising dynamics on random regular graphs

cs.DS math.PRmath-ph ·2026-10-20 ·Zhangsong Li, Allan Sly
similarity 0.61
Abstract · 59 pages, 3 figures

We study Glauber dynamics for the Ising model on random $d$-regular graphs with $n$ vertices at low temperature, in the regime $β\geq C/d$ where $C,d$ are sufficiently large constants. In this regime, the full mixing time is exponential in $n$, because of the bottleneck between the two dominant phases: configurations with a majority of plus spins and configurations with a majority of minus spins. We show that, for sufficiently large $d$, if the dynamics is initialized with an excess of at least $ε_{C,d} n$ plus spins over minus spins, then it quasi-equilibrates in time $O(\log n)$ to the Gibbs measure conditioned on positive magnetization. In addition, the required bias $ε_{C,d}$ can be chosen so that $ε_{C,d}\to 0$ as $d,C\to\infty$. Previous bound of \cite{GSS25+} in the Ising and large-$d$ setting required $β\gtrsim (\log d)/d$. A key difficulty is that, even from the all-plus initialization, one must control the propagation of negative information in spacetime in a low-temperature model with strong local correlations. We address this by developing a new bootstrap approach to proving subcriticality of disagreement clusters under the grand coupling.

0.32