About This Item

Ask the MINDS@UW Librarian

Inapproximability After Uniqueness Phase Transition in Two-Spin Systems

Show full item record

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 
‚Äč

Part of

Show full item record

Search and browse




About MINDS@UW

Deposit materials

  1. Register to deposit in MINDS@UW
  2. Need deposit privileges? Contact us.
  3. Already registered? Have deposit privileges? Deposit materials.