The computational complexity of two‐state spin systems

DOI10.1002/rsa.10090zbMath1030.82001OpenAlexW2122772637MaRDI QIDQ4434468

Leslie Ann Goldberg, Mike S. Paterson, Mark R. Jerrum

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

Ising modelcomputing the partition function

Mathematics Subject Classification ID

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

Related Items (23)

Spatial mixing and the connective constant: optimal bounds ⋮ \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region ⋮ Counting and sampling \(H\)-colourings ⋮ A Graph Polynomial for Independent Sets of Bipartite Graphs ⋮ Complexity of Ising Polynomials ⋮ Computational implications of reducing data to sufficient statistics ⋮ A complexity classification of spin systems with an external field ⋮ Approximating partition functions of the two-state spin system ⋮ Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models ⋮ Complexity classification of the six-vertex model ⋮ Counting Constraint Satisfaction Problems. ⋮ The Ising partition function: zeros and deterministic approximation ⋮ Lee-Yang theorems and the complexity of computing averages ⋮ Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs ⋮ Approximating the partition function of planar two-state spin systems ⋮ Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin ⋮ Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems ⋮ Approximate Counting via Correlation Decay in Spin Systems ⋮ Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results ⋮ Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model ⋮ Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z² ⋮ Unnamed Item ⋮ The complexity of partition functions

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