Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
From MaRDI portal
Publication:2511522
DOI10.1007/s10955-014-0947-5zbMath1297.82009arXiv1107.2368OpenAlexW3081001064MaRDI QIDQ2511522
Alistair Sinclair, Marc Thurley, Piyush Srivastava
Publication date: 6 August 2014
Published in: Journal of Statistical Physics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1107.2368
phase transitionsapproximation algorithmscomplexity theorydecay of correlationstwo-spin systems on trees
Phase transitions (general) in equilibrium statistical mechanics (82B26) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Approximation algorithms (68W25) Statistical mechanics of magnetic materials (82D40)
Related Items
Spatial mixing and the connective constant: optimal bounds, Uniqueness of the Gibbs measure for the 4-state anti-ferromagnetic Potts model on the regular tree, Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction, Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs, Zero-freeness and approximation of real Boolean Holant problems, Computational implications of reducing data to sufficient statistics, Perfect sampling from spatial mixing, Uniqueness of the Gibbs measure for the anti-ferromagnetic Potts model on the infinite \(\Delta \)-regular tree for large \(\Delta \), Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials, Unnamed Item, Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models, Counting Constraint Satisfaction Problems., The Ising partition function: zeros and deterministic approximation, Location of zeros for the partition function of the Ising model on bounded degree graphs, Approximation via Correlation Decay When Strong Spatial Mixing Fails, Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model, Counting hypergraph matchings up to uniqueness threshold, Uniqueness for the 3-state antiferromagnetic Potts model on the tree, Zero-free regions of partition functions with applications to algorithms and graph limits, Fisher zeros and correlation decay in the Ising model, Approximating the partition function of planar two-state spin systems, Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin, Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs, Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems, Fisher Zeros and Correlation Decay in the Ising Model, Exact recovery in the Ising blockmodel, More on zeros and approximation of the Ising partition function, Deterministic counting of graph colourings using sequences of subgraphs, Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions, Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model, The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs, Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs
Cites Work
- On the hardness of sampling independent sets beyond the tree threshold
- Gibbs measures and phase transitions
- Approximating partition functions of the two-state spin system
- Improved mixing condition on the grid for counting and sampling independent sets
- Improved inapproximability results for counting independent sets in the hard-core model
- Counting independent sets up to the tree threshold
- Polynomial-Time Approximation Algorithms for the Ising Model
- On Counting Independent Sets in Sparse Graphs
- The computational complexity of two‐state spin systems
- Computational Complexity
- Correlation Decay up to Uniqueness in Spin Systems
- Approximate Counting via Correlation Decay in Spin Systems
