Inapproximability After Uniqueness Phase Transition in Two-Spin Systems

File(s):

Author(s): Cai, Jin-Yi; Chen, Xi; Guo, Heng; Lu, Pinyan
Citation: TR1715
Date: Dec 2011
Subject(s): Phase Transition; Uniqueness Condition; Complexity; Inapproximability; Spin Systems; Partition Function
Abstract: A two-state spin system is specified by a matrix A = A_{0,0} A_{0,1} A_{1,0} A_{1,1} = beta 1 1 gamma where beta, gamma >= 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 not= RP, for any fixed beta,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(beta,gamma)), where Delta(beta,gamma) > 1/(1- beta gamma) 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 beta, gamma outside the unit square, and all our results generalize to partition functions with an external field.
Permanent link: http://digital.library.wisc.edu/1793/61488
Export: Export to RefWorks