Two-state spin systems with negative interactions

DOI10.1016/J.IC.2025.105340MaRDI QIDQ6884326zbMATH OpenFDO

Authors Yumou Fei, Leslie Ann Goldberg, Pinyan Lu

Publication date 15 December 2025

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2025.105340

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20) Approximation algorithms (68W25) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Cites work

• A Complexity Dichotomy for Partition Functions with Mixed Signs
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• Combinatorics and complexity of partition functions
• Computational transition at the uniqueness threshold
• Computing the independence polynomial: from the tree threshold down to the roots
• Correlation decay and partition function zeros: algorithms and phase transitions
• Correlation decay up to uniqueness in spin systems
• Counting independent sets up to the tree threshold
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Graph homomorphisms with complex values: a dichotomy theorem
• scientific article; zbMATH DE number 1545676 (Why is no real title available?)
• scientific article; zbMATH DE number 7204480 (Why is no real title available?)
• Inapproximability of the independent set polynomial in the complex plane
• Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models
• Inapproximability of the Tutte polynomial
• Lee-Yang theorems and the complexity of computing averages
• On a conjecture of Sokal concerning roots of the independence polynomial
• On complex roots of the independence polynomial
• Polynomial-Time Approximation Algorithms for the Ising Model
• Rapid mixing of Glauber dynamics via spectral independence for all degrees
• Statistical Theory of Equations of State and Phase Transitions. II. Lattice Gas and Ising Model
• The complexity of approximating complex-valued Ising and Tutte partition functions
• The complexity of computing the sign of the Tutte polynomial
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The complexity of partition functions
• The complexity of planar Boolean \(\#\)CSP with complex weights
• The computational complexity of two‐state spin systems
• The computational hardness of counting in two-spin models on d-regular graphs
• Theorems on the Partition Functions of the Heisenberg Ferromagnets
• Zeros of ferromagnetic 2-spin systems
• Zeros of Holant Problems

This page was built for publication: Two-state spin systems with negative interactions

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