Approximation Algorithms for the Random Field Ising Model
From MaRDI portal
Abstract: Approximating the partition function of the ferromagnetic Ising model with general external fields is known to be #BIS-hard in the worst case, even for bounded-degree graphs, and it is widely believed that no polynomial-time approximation scheme exists. This motivates an average-case question: are there classes of instances for which polynomial-time approximation schemes exist? We investigate this question for the random field Ising model on graphs with maximum degree . We establish the existence of fully polynomial-time approximation schemes and samplers with high probability over the random fields if the external fields are IID Gaussians with variance larger than a constant depending only on the inverse temperature and . The main challenge comes from the positive density of vertices at which the external field is small. These regions, which may have connected components of size , are a barrier to algorithms based on establishing a zero-free region, and cause worst-case analyses of Glauber dynamics to fail. The analysis of our algorithm is based on percolation on a self-avoiding walk tree.
Cites work
- scientific article; zbMATH DE number 5485444 (Why is no real title available?)
- A new correlation inequality for Ising models with external fields
- A note on exponential decay in the random field Ising model
- A uniqueness condition for Gibbs measures, with application to the 2- dimensional Ising antiferromagnet
- Algorithmic Pirogov-Sinai theory
- Approximating partition functions of the two-state spin system
- Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
- Combinatorics and complexity of partition functions
- Correlation decay up to uniqueness in spin systems
- Counting independent sets up to the tree threshold
- Efficient sampling and counting algorithms for the Potts model on ℤᵈ at all temperatures
- Exponential decay of correlations in the two-dimensional random field Ising model
- Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
- Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs
- Fisher Zeros and Correlation Decay in the Ising Model
- Improved perturbation expansion for disordered systems: Beating Griffiths singularities
- Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- Percolation and the hard-core lattice gas model
- Polynomial-Time Approximation Algorithms for the Ising Model
- Relaxation of disordered magnets in the Griffiths' regime
- Rounding effects of quenched randomness on first-order phase transitions
- Spatial mixing and the connective constant: optimal bounds
- Taming Griffiths' singularities: Infinite differentiability of quenched correlation functions
- The Complexity of Ferromagnetic Ising with Local Fields
- The complexity of ferromagnetic two-spin systems with external fields
- The hierarchical random field Ising model.
- The relative complexity of approximate counting problems
- Weighted counting of solutions to sparse systems of equations
- \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
Cited in
(4)- Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs
- Fast relaxation of the random field Ising dynamics
- Optimal sufficient requirements on the embedded Ising problem in polynomial time
- An algorithm for finding the first excited state in the random-field Ising model
This page was built for publication: Approximation Algorithms for the Random Field Ising Model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6171258)
