Inapproximability after Uniqueness Phase Transition in Two-Spin Systems

A two-state spin system is specied by a matrixA =A0;0 A0;1A1;0 A1;1= 11 where ; 0. Given an input graph G = (V;E), the partition function ZA(G) of a system is dened asZA(G) =X:V !f0;1gY(u;v)2EA(u);(v): (1)We prove inapproximability results for the partition function in the region specied by the non-uniquenesscondition from phase transition for the Gibbs measure. More specically, assuming NP 6= RP, for anyxed ; in the unit square, there is no randomized polynomial-time algorithm that approximates ZA(G)for d-regular graphs G with relative error = 10􀀀4, if d = ((; )), where (; ) > 1=(1 􀀀 ) isthe uniqueness threshold. Up to a constant factor, this hardness result conrms the conjecture that theuniqueness phase transition coincides with the transition from computational tractability to intractabilityfor ZA(G). We also show a matching inapproximability result for a region of parameters ; outside theunit square, and all our results generalize to partition functions with an external eld.