Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs

DOI10.1017/fms.2022.4OpenAlexW3037009920MaRDI QIDQ5028870

Pjotr Buys, Andreas Galanis, Viresh Patel, Guus Regts

Publication date: 11 February 2022

Published in: Forum of Mathematics, Sigma (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2006.14828

Mathematics Subject Classification ID

Graph polynomials (05C31) Dynamics of complex polynomials, rational maps, entire and meromorphic functions; Fatou and Julia sets (37F10) Approximation algorithms (68W25)

Related Items

Approximating the chromatic polynomial is as hard as computing it exactly, Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial, The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs

Cites Work

• Unnamed Item
• Holant problems for 3-regular graphs with complex edge functions
• Counting in two-spin models on \(d\)-regular graphs
• The worm process for the Ising model is rapidly mixing
• Combinatorics and complexity of partition functions
• The complexity of computing the permanent
• On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs
• Inapproximability of the Tutte polynomial
• Random generation of combinatorial structures from a uniform distribution
• Random cluster dynamics for the Ising model is rapidly mixing
• The complexity of approximating complex-valued Ising and Tutte partition functions
• The Ising partition function: zeros and deterministic approximation
• The relative complexity of approximate counting problems
• Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
• Cayley trees do not determine the maximal zero-free locus of the independence polynomial
• On a conjecture of Sokal concerning roots of the independence polynomial
• Limiting measure of Lee-Yang zeros for the Cayley tree
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• Theory of monomer-dimer systems
• The Complexity of Ferromagnetic Two-spin Systems with External Fields
• Polynomial-Time Approximation Algorithms for the Ising Model
• Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region
• Location of zeros for the partition function of the Ising model on bounded degree graphs
• Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials
• On the topological structure of the arithmetic sum of two Cantor sets
• The Complexity of Computing the Sign of the Tutte Polynomial
• Inapproximability of the Independent Set Polynomial in the Complex Plane
• Quantum algorithms for classical lattice models
• Zeros of ferromagnetic 2-spin systems
• Fisher zeros and correlation decay in the Ising model
• Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems
• Weighted counting of solutions to sparse systems of equations
• Zeros of Holant problems: locations and algorithms
• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• Dynamics in One Complex Variable. (AM-160)
• Correlation Decay up to Uniqueness in Spin Systems
• Statistical Theory of Equations of State and Phase Transitions. I. Theory of Condensation
• Statistical Theory of Equations of State and Phase Transitions. II. Lattice Gas and Ising Model