Eric Vigoda, Computational Phase Transitions for the Potts Model

This is a followup talk to my CS colloquium on March 2. In that talk I discussed the problems of counting independent sets and colorings. Those problems are examples of antiferromagnetic systems in which neighboring vertices prefer different assignments. In this talk we will look at ferromagnetic systems where neighboring vertices prefer the same assignment. We will focus on the ferromagnetic Potts model. We will look at the phase transitions in this model, and their connections to the complexity of associated counting/sampling problems and the performance of related Markov chains.
The talk is based on joint works with Andreas Galanis, Daniel Stefankovic, and Linji Yang.