| Title: | Phase Transitions in the Complexity of Counting |
| Advisor: | Dr.Eric Vigoda , School of Computer Science |
| Committee: | Dr.William Perkins, School of Mathematics |
| Dr. Dana Randall, School of Computer Science | |
| Dr. Daniel Stefankovic, Department of Computer Science, University of Rochester | |
| Dr. Prasad Tetali, School of Mathematics | |
| Dr. Santosh Vempala, School of Computer Science | |
| Reader: | Dr. Prasad Tetali, School of Mathematics |
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 \Delta undergoes a phase 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 they 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 k-colorings, q-state antiferromagnetic Potts model and antiferromagnetic 2-spin systems. The criterion captures in an appropriate way the statistical physics uniqueness phase transition on the tree.
