Phase transitions in the complexity of counting

Abstract

A recent line of works established a remarkable connection 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 \Delta undergoes a computational transition that coincides with the statistical physics uniqueness/non-uniqueness phase transition on the infinite \Delta-regular tree. Despite this clear picture for 2-spin systems, there is little known for multi-spin systems. We present the first analog of the above inapproximability results for multi-spin systems.

The main difficulty in previous inapproximability results was analyzing the behavior of the model on random \Delta-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). We thus obtain a generic analysis of the Gibbs distribution of any multi-spin system on random regular bipartite graphs. We also treat in depth the k-colorings and the q-state antiferromagnetic Potts models.

Based on these findings, we prove that for \Delta constant and even k<\Delta, it is NP-hard to approximate within an exponential factor the number of k-colorings on triangle-free \Delta-regular graphs. We also prove an analogous statement for the antiferromagnetic Potts model. Our hardness results for these models complement the conjectured regime where the models are believed to have efficient approximation schemes. We systematize the approach to obtain a general theorem for the computational hardness of counting in antiferromagnetic spin systems, which we ultimately use to obtain the inapproximability results for the k-colorings and q-state antiferromagnetic Potts models, as well as (the previously known results for) antiferromagnetic 2-spin systems. The criterion captures in an appropriate way the statistical physics uniqueness phase transition on the tree.