## 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.

##### Subject

Phase Transition

Uniqueness Condition

Complexity

Inapproximability

Spin Systems

Partition Function

##### Permanent Link

http://digital.library.wisc.edu/1793/61488##### Citation

TR1715