Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness RegionInapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region

Access Restriction
Subscribed

 Author Galanis, Andreas ♦ tefankovi, Daniel ♦ Vigoda, Eric Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2015 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Approximate counting ♦ Inapproximability ♦ Phase transitions ♦ Random regular graphs Abstract A remarkable connection has been established for antiferromagnetic 2-spin systems, including the Ising and hard-core models, showing that the computational complexity of approximating the partition function for graphs with maximum degree Δ undergoes a phase transition that coincides with the statistical physics uniqueness/nonuniqueness phase transition on the infinite Δ-regular tree. Despite this clear picture for 2-spin systems, there is little known for multispin systems. We present the first analog of this in approximability results for multispin systems. The main difficulty in previous inapproximability results was analyzing the behavior of the model on random Δ-regular bipartite graphs, which served as the gadget in the reduction. To this end, one needs to understand the moments of the partition function. Our key contribution is connecting: (i) induced matrix norms, (ii) maxima of the expectation of the partition function, and (iii) attractive fixed points of the associated tree recursions (belief propagation). The view through matrix norms allows a simple and generic analysis of the second moment for any spin system on random Δ-regular bipartite graphs. This yields concentration results for any spin system in which one can analyze the maxima of the first moment. The connection to fixed points of the tree recursions enables an analysis of the maxima of the first moment for specific models of interest. For $\textit{k}-colorings$ we prove that for even $\textit{k},$ in a tree nonuniqueness region (which corresponds to $\textit{k}$ < Δ) there is no FPRAS, unless NP = RP, to approximate the number of colorings for triangle-free Δ-regular graphs. Our proof extends to the antiferromagnetic Potts model, and, in fact, to every antiferromagnetic model under a mild condition. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2015-12-10 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 62 Issue Number 6 Page Count 60 Starting Page 1 Ending Page 60

Open content in new tab

Source: ACM Digital Library