Correlation decay up to uniqueness in spin systems

DOI10.1137/1.9781611973105.5MaRDI QIDQ5741713zbMATH OpenOpenAlexFDO

Authors Liang Li, Pinyan Lu, Yitong Yin

Publication date 15 May 2019

Published in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.7064

Mathematics Subject Classification ID

Distance in graphs (05C12) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Analysis of algorithms (68W40) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Abstract: We give a complete characterization of the two-state anti-ferromagnetic spin systems which are of strong spatial mixing on general graphs. We show that a two-state anti-ferromagnetic spin system is of strong spatial mixing on all graphs of maximum degree at most $Delta$ if and only if the system has a unique Gibbs measure on infinite regular trees of degree up to $Delta$, where $Delta$ can be either bounded or unbounded. As a consequence, there exists an FPTAS for the partition function of a two-state anti-ferromagnetic spin system on graphs of maximum degree at most $Delta$ when the uniqueness condition is satisfied on infinite regular trees of degree up to $Delta$. In particular, an FPTAS exists for arbitrary graphs if the uniqueness is satisfied on all infinite regular trees. This covers as special cases all previous algorithmic results for two-state anti-ferromagnetic systems on general-structure graphs. Combining with the FPRAS for two-state ferromagnetic spin systems of Jerrum-Sinclair and Goldberg-Jerrum-Paterson, and the hardness results of Sly-Sun and independently of Galanis-Stefankovic-Vigoda, this gives a complete classification, except at the phase transition boundary, of the approximability of all two-state spin systems, on either degree-bounded families of graphs or family of all graphs.

Recommendations

• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• Approximating partition functions of the two-state spin system
• Uniqueness, spatial mixing, and approximation for ferromagnetic 2-spin systems

Cited in

(74)

• Uniqueness and exponential decay of correlations for some two-dimensional spin lattice systems.
• Complexity classification of the six-vertex model
• The Ising partition function: zeros and deterministic approximation
• Counting hypergraph matchings up to uniqueness threshold
• Strong decay to equilibrium in one-dimensional random spin systems
• Approximating partition functions of the two-state spin system
• 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
• Uniqueness of Gibbs measures for continuous hardcore models
• Spatial mixing and the connective constant: optimal bounds
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• A dichotomy for bounded degree graph homomorphisms with nonnegative weights
• \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• Analyticity for classical gasses via recursion
• The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
• Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z²
• Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs
• Approximation via correlation decay when strong spatial mixing fails
• 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
• More on zeros and approximation of the Ising partition function
• Counting constraint satisfaction problems
• Swendsen-Wang dynamics for general graphs in the tree uniqueness region
• 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
• A spectral independence view on hard spheres via block dynamics
• Fast algorithms for general spin systems on bipartite expanders
• Fisher Zeros and Correlation Decay in the Ising Model
• Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing
• Fisher zeros and correlation decay in the Ising model
• Uniqueness, spatial mixing, and approximation for ferromagnetic 2-spin systems
• Strong spatial mixing of list coloring of graphs
• Strong spatial mixing in homomorphism spaces
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• Approximate counting via correlation decay in spin systems
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• scientific article; zbMATH DE number 7650115 (Why is no real title available?)
• 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
• Perfect sampling from spatial mixing
• Approximability of the complementarily symmetric Holant problems on cubic graphs
• Correlation decay and the absence of zeros property of partition functions
• Uniqueness of the Gibbs measure for the anti-ferromagnetic Potts model on the infinite -regular tree for large
• A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory
• Near-Optimal Distributed Linear-Quadratic Regulator for Networked Systems
• Approximation Algorithms for the Random Field Ising Model
• Online Edge Coloring via Tree Recurrences and Correlation Decay
• 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
• A dichotomy for bounded degree graph homomorphisms with nonnegative weights
• Approximate counting for spin systems in sub-quadratic time
• Two-state spin systems with negative interactions
• 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
• Analyticity for locally stable hard-core gases via recursion
• Approximate counting for spin systems in sub-quadratic time
• Bounded degree nonnegative counting CSP
• Inapproximability of counting hypergraph colourings
• Fast sampling via spectral independence beyond bounded-degree graphs
• Optimal network control of spatially exponential decaying linear quadratic regulator
• A spectral independence view on hard spheres via block dynamics
• An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution
• Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion
• Improved mixing of critical hardcore model
• Sink-free orientations: a local sampler with applications
• Approximating the partition function of planar two-state spin systems
• Finitary codings for spatial mixing Markov random fields
• An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes

This page was built for publication: Correlation decay up to uniqueness in spin systems

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