This talk will focus on connections between phase transitions and the computational complexity of approximating the partition function of spin systems. A principal example of such a connection is in the context of approximating the number of independent sets in graphs of bounded degree, where the uniqueness threshold on the infinite regular tree pinpoints the boundary of efficient computation. 

 

We will be interested in similar connections for spin systems on bounded degree graphs. Examples of the computational problems we will consider are: 

(i) approximately counting colorings,

(ii) approximately counting independent sets on bipartite graphs (#BIS),

(iii) approximating the partition function of the ferromagnetic Potts model.

Based on the phase transitions of the models, we will discuss hardness results for these problems on bounded degree graphs.

 

Joint work with: Jin-Yi Cai, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic, and Eric Vigoda.