Title:
Computing partition functions by interpolation
Speaker:
Alexander Barvinok (UMICH)
Abstract:
Partition functions are just multivariate polynomials with great many monomials enumerating combinatorial structures of a particular type
and their efficient computation (approximation) are of interest for combinatorics, statistics, physics and computational complexity. I’ll present a general principle: the partition function can be efficiently approximated in a domain if it has no complex zeros
in a slightly larger domain, and illustrate it on the examples of the permanent of a matrix, the independence polynomial of a graph and, time permitting, the graph homomorphism partition function.
Alexander Barvinok is a professor of mathematics at the University of Michigan, Ann Arbor. He is interested in computational complexity and
algorithms in algebra, geometry and combinatorics.