Lee-Yang theorems and the complexity of computing averages
==========================================================


In a seminal paper, Lee and Yang (1952) initiated the study of the
location of zeroes of the partition function of the ferromagnetic
Ising model.  They showed that these zeroes lie on the unit circle in
the complex plane, and used this property to study the phase
transition phenomenon.  Over the years, several important extensions
to the Lee-Yang theorem were proved for other models in statistical
physics, which included many generalizations of the Ising model, and
also the so called monomer-dimer model, which corresponds to
exponentially weighted matchings.

In this work, we relate the location of zeroes of the partition
function to the #P-hardness of computing averages in these models.
For the ferromagnetic Ising model, we prove a new extension of the
classical Lee-Yang theorem, and use it to prove #P-hardness of
computing the magnetization.  For the monomer-dimer model, we use a
similar extension due to Heilmann and Lieb to prove the #P-hardness of
computing the average size of exponentially weighted matchings.

The talk would not assume any background in statistical physics.  This
is based on joint work with Alistair Sinclair.