Spring 2019

Lee-Yang Zeros and the Complexity of the Ferromagnetic Ising Model on Bounded-Degree Graphs

Thursday, September 10th, 2020 12:10 pm12:50 pm

Add to Calendar


Guus Regts (University of Amsterdam)

I will speak about the complexity of approximating the partition function of the ferromagnetic Ising model on bounded-degree graphs for complex valued external field parameters. In short, utilizing the Lee-Yang theorem, Liu, Sinclair and Srivastava showed that the partition function is easy to approximate inside and outside the unit circle, but we show that it is hard (#P-hard) to approximate on the unit circle. This indicates a connection between the presence of (Lee-Yang) zeros and hardness of approximation.

Complex dynamics plays a central role in both the hardness proof and the proof for the density of the Lee-Yang zeros on the unit circle. I will explain this and state some open questions related to this.

Based on joint work with Pjotr Buys, Andreas Galanis and Viresh Patel.