Inapproximability after Uniqueness Phase Transition in Two-Spin Systems

Jin-Yi Cai, Xi Chen, Heng Guo, Pinyan Lu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.
Original languageEnglish
Title of host publicationCombinatorial Optimization and Applications - 6th International Conference, COCOA 2012, Banff, AB, Canada, August 5-9, 2012. Proceedings
Pages336-347
Number of pages12
ISBN (Electronic)978-3-642-31770-5
DOIs
Publication statusPublished - 29 Apr 2012
EventCOCOA 2012 - Banff, Canada
Duration: 5 Aug 20129 Aug 2012
http://webdocs.cs.ualberta.ca/~ghlin/COCOA2012/

Conference

ConferenceCOCOA 2012
Country/TerritoryCanada
CityBanff
Period5/08/129/08/12
Internet address

Fingerprint

Dive into the research topics of 'Inapproximability after Uniqueness Phase Transition in Two-Spin Systems'. Together they form a unique fingerprint.

Cite this