PACM Colloquium: Alexander Barvinok, University of Michigan, Ann Arbor

Computational complexity of approximation and complex zeros

In this talk, we are interested in efficient approximate computation of complicated combinatorially defined multivariate polynomials. A typical example is provided by the permanent of an nxn complex matrix, which is a polynomial with n! terms of degree n in n^2 complex variables. It turns out that such polynomials can be efficiently approximated in a complex domain, provided they have no zeros in a slightly larger domain. I will illustrate this general simple idea on the examples of the permanent (also known as the partition function of dimer coverings), matching polynomial (also known as the partition function of the monomer-dimer model) and, time permitting, the independence polynomial (also known as the partition function in the hard core model). Connections to the Lee-Yang theory of phase transition will be discussed.

Alexander Barvinok is a professor of mathematics at the University of Michigan in Ann Arbor. He is interested in computational complexity and algorithms in algebra, geometry and combinatorics.