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

Mon, Sep 23, 2019, 4:00 pm

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.

214 Fine Hall
Event category: 

Upcoming Events

PACM Colloquium: Philip Rosenau, Tel-Aviv University

Mon, Oct 21, 2019, 4:00 pm
Location: 214 Fine Hall

Graduate Student Seminar: Spectral volumes for heterogeneity in cryo-EM, Speaker: Amit Halevi

Analysis of Fluids and Related Topics: Shapes of equilibrium capillary drops on a rough surface, William Feldman, University of Chicago