Abstract
Part of the importance of the partition function in the study of spin systems comes from the fact that the derivatives of its logarithm (i.e., derivatives of the free energy) encode mean values of natural observables of these spin systems. Examples of such mean observables include the mean energy and the mean magnetization in the Ising model, the average size of matchings in the monomer-dimer model, and the average size of independent sets in the hard core lattice gas model. However, unlike the case of partition functions, not much was not until recently about the computational complexity of exactly computing such mean observables.
In this talk, we describe some recent results establishing the #P hardness of all the mean observables listed above. We also point out connections with the study of complex zeros of partition functions that arose in the course of proving these results.
This talk is based on joint work with Leonard J. Schulman and Alistair Sinclair.