The Complexity of Ferromagnetic Ising with Local Fields

DOI10.1017/S096354830600767XzbMath1170.82001OpenAlexW1977162457MaRDI QIDQ3429740

Leslie Ann Goldberg, Mark R. Jerrum

Publication date: 20 March 2007

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s096354830600767x

zbMATH Keywords

ferromagnetic Ising modelferromagnetic \(q\)-state Potts modelcomplexity of approximating the partition function

Mathematics Subject Classification ID

Combinatorial probability (60C05) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (24)

\(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region ⋮ Completeness Results for Counting Problems with Easy Decision ⋮ On some properties of the low-dimensional Gumbel perturbations in the perturb-and-MAP model ⋮ Approximately counting locally-optimal structures ⋮ Approximately Counting Locally-Optimal Structures ⋮ Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models ⋮ A Graph Polynomial for Independent Sets of Bipartite Graphs ⋮ Low depth quantum circuits for Ising models ⋮ The Complexity of Approximately Counting Tree Homomorphisms ⋮ Polynomial-time algorithms for multimarginal optimal transport problems with structure ⋮ Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields ⋮ Approximately counting independent sets in bipartite graphs via graph containers ⋮ Commuting quantum circuits and complexity of Ising partition functions ⋮ A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory ⋮ A complexity classification of spin systems with an external field ⋮ Approximation Algorithms for the Random Field Ising Model ⋮ The complexity of approximately counting stable roommate assignments ⋮ The complexity of approximately counting stable matchings ⋮ Counting Constraint Satisfaction Problems. ⋮ The Tutte-Potts connection in the presence of an external magnetic field ⋮ Approximately Counting $H$-Colorings is $\#\mathrm{BIS}$-Hard ⋮ Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin ⋮ Unnamed Item ⋮ Functional clones and expressibility of partition functions

This page was built for publication: The Complexity of Ferromagnetic Ising with Local Fields