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.
|Title of host publication||Combinatorial Optimization and Applications - 6th International Conference, COCOA 2012, Banff, AB, Canada, August 5-9, 2012. Proceedings|
|Number of pages||12|
|Publication status||Published - 29 Apr 2012|
|Event||COCOA 2012 - Banff, Canada|
Duration: 5 Aug 2012 → 9 Aug 2012
|Period||5/08/12 → 9/08/12|