Title: Zeros of polynomials and the computational complexity of problems in statistical physics
Abstract:
Spin systems such as the Ising model originated in statistical physics as a tool for the qualitative study of phase transitions in phenomena like magnetism. They have since found applications in the modeling of other complex systems. e.g., in the study of social networks and in machine learning. In this work, we study the computational complexity of computing mean statistics of such models (e.g., the magnetization of the Ising model), and relate these questions to the location of the complex zeros of the "partition function" (a well studied generating polynomial of the probability distribution specified by such a model).
In two seminal papers, Lee and Yang [1952] initiated the study of the zeros of the partition function, and related phase transitions in the Ising model to the location of such zeros. To use this connection, they then proved the striking theorem that the zeros of the partition function of the so-called "ferromagnetic" Ising model lie on the unit circle in the complex plane. The study of the location of zeros of other classes of polynomials has an even longer history, and also has applications in probability theory and combinatorics.
In this talk, we will briefly survey the Lee-Yang theorem and its connection to phase transitions, and then present our recent extension of the Lee-Yang theorem which has applications to proving the #P-hardness of computing the magnetization of the Ising model. We will also present another example of our method of using results about locations of zeros of polynomials to prove #P-hardness by applying it to the problem of computing the average size of a matching in the monomer-dimer model.
This talk is based on joint work with Alistair Sinclair.
