Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
From MaRDI portal
Publication:2511522
Abstract: In a seminal paper (Weitz, 2006), Weitz gave a deterministic fully polynomial approximation scheme for count- ing exponentially weighted independent sets (equivalently, approximating the partition function of the hard-core model from statistical physics) on graphs of degree at most d, up to the critical activity for the uniqueness of the Gibbs measure on the infinite d-regular tree. More recently Sly (Sly, 2010) showed that this is optimal in the sense that if there is an FPRAS for the hard-core partition function on graphs of maximum degree d for activities larger than the critical activity on the infinite d-regular tree then NP = RP. In this paper, we extend Weitz's approach to derive a deterministic fully polynomial approx- imation scheme for the partition function of the anti-ferromagnetic Ising model with arbitrary field on graphs of maximum degree d, up to the corresponding critical point on the d-regular tree. The main ingredient of our result is a proof that for two-state anti-ferromagnetic spin systems on the d-regular tree, weak spatial mixing implies strong spatial mixing. This in turn uses a message-decay argument which extends a similar approach proposed recently for the hard-core model by Restrepo et al (Restrepo et al, 2011) to the case of the anti-ferromagnetic Ising model with arbitrary field. By a standard correspondence, these results translate to arbitrary two-state anti-ferromagnetic spin systems with soft constraints.
Recommendations
- Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
- Correlation decay up to uniqueness in spin systems
- Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems
- Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models
- Counting in two-spin models on \(d\)-regular graphs
Cites work
- Approximate counting via correlation decay in spin systems
- Approximating partition functions of the two-state spin system
- Computational Complexity
- Correlation decay up to uniqueness in spin systems
- Counting independent sets up to the tree threshold
- Gibbs measures and phase transitions
- On Counting Independent Sets in Sparse Graphs
- On the hardness of sampling independent sets beyond the tree threshold
- Polynomial-Time Approximation Algorithms for the Ising Model
- The computational complexity of two‐state spin systems
Cited in
(50)- The Ising partition function: zeros and deterministic approximation
- Counting hypergraph matchings up to uniqueness threshold
- Zero-free regions of partition functions with applications to algorithms and graph limits
- Uniqueness for the 3-state antiferromagnetic Potts model on the tree
- Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
- Zero-freeness and approximation of real Boolean Holant problems
- Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
- Exact recovery in the Ising blockmodel
- 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
- The complexity of ferromagnetic two-spin systems with external fields
- Inapproximability after uniqueness phase transition in two-spin systems
- Location of zeros for the partition function of the Ising model on bounded degree graphs
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- 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 in two-spin models on \(d\)-regular graphs
- More on zeros and approximation of the Ising partition function
- Deterministic counting of graph colourings using sequences of subgraphs
- Counting constraint satisfaction problems
- Sampling in uniqueness from the Potts and random-cluster models on random regular graphs
- Spectral independence in high-dimensional expanders and applications to the hardcore model
- Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs
- Fisher Zeros and Correlation Decay in the Ising Model
- Fisher zeros and correlation decay in the Ising model
- Uniqueness, spatial mixing, and approximation for ferromagnetic 2-spin systems
- Sampling in uniqueness from the Potts and random-cluster models on random regular graphs
- Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models
- Correlation decay up to uniqueness in spin systems
- Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
- The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs
- 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
- Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs
- Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs
- Perfect sampling from spatial mixing
- Uniqueness of the Gibbs measure for the anti-ferromagnetic Potts model on the infinite -regular tree for large
- The complexity of ferromagnetic 2-spin systems on bounded degree graphs
- Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
- Two-state spin systems with negative interactions
- Fast and slow mixing of the Kawasaki dynamics on bounded-degree graphs
- Two-state spin systems with negative interactions
- Influence maximization in Ising models
- On sampling from Ising models with spectral constraints
- Correlation decay and partition function zeros: algorithms and phase transitions
- Near optimal bounds for weak and strong spatial mixing for the anti-ferromagnetic Potts model on trees
- Approximate counting for spin systems in sub-quadratic time
- Bounded degree nonnegative counting CSP
- Approximating the partition function of planar two-state spin systems
- Computational implications of reducing data to sufficient statistics
This page was built for publication: Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2511522)
