Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models

DOI10.1017/S0963548315000401zbMath1420.68098arXiv1203.2226OpenAlexW1776308369MaRDI QIDQ5366911

Eric Vigoda, Daniel Štefanković, Andreas Galanis

Publication date: 10 October 2017

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (44)

\(\#\)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 ⋮ A spectral condition for spectral gap: fast mixing in high-temperature Ising models ⋮ Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs ⋮ Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models ⋮ Zero-freeness and approximation of real Boolean Holant problems ⋮ The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs ⋮ An FPTAS for the hardcore model on random regular bipartite graphs ⋮ Algorithmic Pirogov-Sinai theory ⋮ Computational implications of reducing data to sufficient statistics ⋮ Efficient sampling and counting algorithms for the Potts model on ℤ^d at all temperatures ⋮ Perfect sampling from spatial mixing ⋮ What can be sampled locally? ⋮ Approximability of the complementarily symmetric Holant problems on cubic graphs ⋮ Uniqueness of the Gibbs measure for the anti-ferromagnetic Potts model on the infinite \(\Delta \)-regular tree for large \(\Delta \) ⋮ One-step replica symmetry breaking of random regular NAE-SAT. II ⋮ Inapproximability of counting independent sets in linear hypergraphs ⋮ Exact distributed sampling ⋮ Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs ⋮ Factor models on locally tree-like graphs ⋮ Large scale stochastic dynamics. Abstracts from the workshop held September 15--21, 2019 ⋮ 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 ⋮ Bethe states of random factor graphs ⋮ Counting Independent Sets and Colorings on Random Regular Bipartite Graphs ⋮ Calculating eigenvalues of many-body systems from partition functions ⋮ Algorithms for #BIS-Hard Problems on Expander Graphs ⋮ Counting hypergraph matchings up to uniqueness threshold ⋮ Uniqueness for the 3-state antiferromagnetic Potts model on the tree ⋮ Mixing of Markov chains for independent sets on chordal graphs with bounded separators ⋮ 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 ⋮ More on zeros and approximation of the Ising partition function ⋮ Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results ⋮ Efficient algorithms for approximating quantum partition functions ⋮ Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model ⋮ Unnamed Item ⋮ Dynamic Sampling from Graphical Models ⋮ Implementations and the independent set polynomial below the Shearer threshold ⋮ 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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Counting in two-spin models on \(d\)-regular graphs
• The self-dual point of the two-dimensional random-cluster model is critical for \(q \geqslant 1\)
• On the hardness of sampling independent sets beyond the tree threshold
• Gibbs measures and phase transitions
• The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
• Glauber dynamics on trees: Boundary conditions and mixing time
• Approximating partition functions of the two-state spin system
• Improved mixing condition on the grid for counting and sampling independent sets
• Factor models on locally tree-like graphs
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• Improved inapproximability results for counting independent sets in the hard-core model
• Polynomial-Time Approximation Algorithms for the Ising Model
• On Counting Independent Sets in Sparse Graphs
• Information, Physics, and Computation
• The Complexity of Enumeration and Reliability Problems
• The computational complexity of two‐state spin systems
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• Fast mixing for independent sets, colorings, and other models on trees
• The two possible values of the chromatic number of a random graph

This page was built for publication: Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models