Correlation Decay up to Uniqueness in Spin Systems

DOI10.1137/1.9781611973105.5zbMath1422.68302arXiv1111.7064OpenAlexW4214828486MaRDI QIDQ5741713

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

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

Related Items (45)

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 ⋮ 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 ⋮ A Spectral Independence View on Hard Spheres via Block Dynamics ⋮ Zero-freeness and approximation of real Boolean Holant problems ⋮ The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs ⋮ Perfect sampling from spatial mixing ⋮ Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs ⋮ A dichotomy for bounded degree graph homomorphisms with nonnegative weights ⋮ 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 \(\Delta \)-regular tree for large \(\Delta \) ⋮ 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 ⋮ Unnamed Item ⋮ Online Edge Coloring via Tree Recurrences and Correlation Decay ⋮ Unnamed Item ⋮ Analyticity for classical gasses via recursion ⋮ Complexity classification of the six-vertex model ⋮ Counting Constraint Satisfaction Problems. ⋮ The Ising partition function: zeros and deterministic approximation ⋮ 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 ⋮ Strong spatial mixing in homomorphism spaces ⋮ An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution ⋮ Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs ⋮ 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 ⋮ 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 ⋮ Uniqueness of Gibbs measures for continuous hardcore models ⋮ 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 ⋮ Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions ⋮ Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results ⋮ 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

This page was built for publication: Correlation Decay up to Uniqueness in Spin Systems