The computational complexity of two‐state spin systems

DOI10.1002/RSA.10090MaRDI QIDQ4434468zbMATH OpenOpenAlexFDO

Authors Leslie Ann Goldberg, Mark Jerrum, Mike Paterson

Publication date 10 November 2003

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL http://wrap.warwick.ac.uk/61194/7/WRAP_cs-rr-386.pdf

zbMATH Keywords

computing the partition functionIsing model

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Recommendations

• A complexity classification of spin systems with an external field
• The Complexity of Ferromagnetic Ising with Local Fields
• Counting in two-spin models on \(d\)-regular graphs
• Approximating the partition function of planar two-state spin systems
• Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models

Cited in

(36)

• Complexity classification of the six-vertex model
• The Ising partition function: zeros and deterministic approximation
• Counting and sampling \(H\)-colourings
• Approximating partition functions of the two-state spin system
• Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
• Computing the partition function of the Sherrington-Kirkpatrick model is hard on average
• Lee-Yang theorems and the complexity of computing averages
• Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
• Spatial mixing and the connective constant: optimal bounds
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• The complexity of partition functions
• \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• A graph polynomial for independent sets of bipartite graphs
• Complexity of Ising polynomials
• A complexity classification of spin systems with an external field
• Symbolic computation methods for some spin glasses problems
• The complexity of ferromagnetic two-spin systems with external fields
• Computational hardness of enumerating groundstates of the antiferromagnetic Ising model in triangulations
• The Complexity of Ferromagnetic Ising with Local Fields
• Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z²
• FPTAS for hardcore and Ising models on hypergraphs
• Counting in two-spin models on \(d\)-regular graphs
• A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory
• Counting constraint satisfaction problems
• Spectral independence in high-dimensional expanders and applications to the hardcore model
• Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models
• Lee-Yang theorems and the complexity of computing averages
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• Approximate counting via correlation decay in spin systems
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• The complexity of ferromagnetic 2-spin systems on bounded degree graphs
• Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
• Two-state spin systems with negative interactions
• Two-state spin systems with negative interactions
• Approximating the partition function of planar two-state spin systems
• Computational implications of reducing data to sufficient statistics

This page was built for publication: The computational complexity of two‐state spin systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4434468)