Colloquium: "Complex Geometry and Computational Complexity"

Alexander Barvinok, University of Michigan

Abstract: I’ll describe how the absence of complex zeros of a multivariate polynomial in a certain domain allows one to efficiently compute (approximate) the polynomial in the domain. The main example will be the permanent of a matrix (which looks just like the determinant, only simpler: all monomials are counted with the “+” sign). Another example is the independence polynomial of a graph, also known as the partition function of a hard core model in statistical physics.

 

Host: Todd Kuffner & John Shareshian
Tea @ 3:45pm in Cupples I, Room 200