Phase Transition and Computational Transition

Heng Guo ( University Wisconsin-Madison )

Spin systems is a general framework modeling nearest-neighbour interactions on graphs. Each vertex may be assigned one of q states and the edge interaction may be either attractive (ferromagnetic) or repulsive (anti-ferromagnetic). In this talk we will focus on anti-ferromagnetic 2-spin systems. Recently there has been great progress on classifying the complexity of approximating the partition function of such systems. An important observation is that the computational transition coincides with the uniqueness phase transition discovered in statistical physics. Moreover, this coincidence also holds if the graph is bipartite. We will discuss both the algorithm and the hardness proof.