Inapproximability after uniqueness phase transition in two-spin systems

DOI10.1007/978-3-642-31770-5_30MaRDI QIDQ3167375zbMATH OpenOpenAlexFDO

Authors Jin-Yi Cai, Xi Chen, Heng Guo, Pinyan Lu

Publication date 2 November 2012

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44)

Abstract: A two-state spin system is specified by a 2 x 2 matrix A = {A_{0,0} A_{0,1}, A_{1,0} A_{1,1}} = {�eta 1, 1 gamma} where �eta, gamma ge 0. Given an input graph G=(V,E), the partition function Z_A(G) of a system is defined as Z_A(G) = sum_{sigma: V -> {0,1}} prod_{(u,v) in E} A_{sigma(u), sigma(v)} We prove inapproximability results for the partition function in the region specified by the non-uniqueness condition from phase transition for the Gibbs measure. More specifically, assuming NP e RP, for any fixed �eta, gamma in the unit square, there is no randomized polynomial-time algorithm that approximates Z_A(G) for d-regular graphs G with relative error epsilon = 10^{-4}, if d = Omega(Delta(�eta,gamma)), where Delta(�eta,gamma) > 1/(1-�etagamma) is the uniqueness threshold. Up to a constant factor, this hardness result confirms the conjecture that the uniqueness phase transition coincides with the transition from computational tractability to intractability for Z_A(G). We also show a matching inapproximability result for a region of parameters �eta, gamma outside the unit square, and all our results generalize to partition functions with an external field.

Recommendations

• Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models
• Approximating the partition function of planar two-state spin systems
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs

Cited in

(8)

• Approximating partition functions of the two-state spin system
• \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
• Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems
• Beyond windability: approximability of the four-vertex model
• Inapproximability of counting hypergraph colourings
• Approximating the partition function of planar two-state spin systems
• Computational implications of reducing data to sufficient statistics

This page was built for publication: Inapproximability after uniqueness phase transition in two-spin systems

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