Inapproximability After Uniqueness Phase Transition in TwoSpin Systems
Show full item record
File(s):
 Author(s)

Cai, JinYi; 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 twostate 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 nonuniqueness 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 polynomialtime algorithm that approximates Z_A(G) for dregular 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
Part of
Show full item record