Inapproximability After Uniqueness Phase Transition in Two-Spin Systems

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.