UAlberta Math and Statistics Colloquium: Alexander Barvinok

On a few examples, such as the permanent of a matrix, (partition function for a system of bosons), matching polynomial of a graph (partition function in a monomer-dimer system), and the independence polynomial of a graph (partition function in the hard core model), we illustrate how the computational complexity of approximation is related to complex zeros (even if we want to approximate in a real domain) and to the phase transition in the Lee - Yang sense. The idea is roughly as follows: a combinatorially defined multivariate polynomial can be efficiently approximated in a complex domain, if it does not have zeros in a slightly larger domain.