Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Spin systems (e.g., the Ising model) originated in statistical physics as a tool for the qualitative study of phase transitions in phenomena such as magnetism.  However, they have also been applied to the modeling of other complex systems, e.g., in the study of social networks and in machine learning, and various computational problems associated with them have received much attention in the literature.  In this work, we study the computational complexity of computing mean statistics of spin systems, e.g., the magnetization of the Ising model, and relate these questions to the location of the complex zeros of the partition function. (In addition to their importance in statistical physics, partition functions are also of interest in computational complexity theory where they form canonical examples of problems known to be hard for the class #P of counting problems.) In this talk, we will briefly survey the Lee-Yang theorem and its connection to phase transitions. We will then present our recent extension of the Lee-Yang theorem, and its application to proving that computing the magnetization of the ferromagnetic Ising model is #P-hard. 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 dimer count in the monomer-dimer model. This talk is based on joint work with Alistair Sinclair.