A complexity classification of spin systems with an external field

DOI10.1073/PNAS.1505664112MaRDI QIDQ2962306zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Leslie Ann Goldberg, Mark Jerrum

Publication date 16 February 2017

Published in Proceedings of the National Academy of Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1073/pnas.1505664112

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Recommendations

• The complexity of ferromagnetic two-spin systems with external fields
• The Complexity of Ferromagnetic Ising with Local Fields
• The computational complexity of two‐state spin systems
• The complexity of approximating complex-valued Ising and Tutte partition functions
• Automata, Languages and Programming

Cites work

• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
• Polynomial-Time Approximation Algorithms for the Ising Model
• Probability and Computing
• Random generation of combinatorial structures from a uniform distribution
• The complexity of approximating conservative counting CSPs
• The complexity of conservative valued CSPs
• The Complexity of Ferromagnetic Ising with Local Fields
• The complexity of partition functions
• The computational complexity of two‐state spin systems
• The cone of Monge matrices: Extremal rays and applications
• The expressibility of functions on the Boolean domain, with applications to counting CSPs
• The relative complexity of approximate counting problems

Cited in

(14)

• An FPTAS for the hardcore model on random regular bipartite graphs
• A fixed-parameter perspective on \#BIS
• Functional clones and expressibility of partition functions
• The complexity of ferromagnetic two-spin systems with external fields
• Completeness of classical spin models and universal quantum computation
• The Complexity of Ferromagnetic Ising with Local Fields
• The computational complexity of two‐state spin systems
• The complexity of translationally invariant low-dimensional spin lattices in 3D
• A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory
• Counting constraint satisfaction problems
• A fixed-parameter perspective on \#BIS
• On the permanents of circulant and degenerate Schur matrices
• Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
• Bounded degree nonnegative counting CSP

This page was built for publication: A complexity classification of spin systems with an external field

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