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

ANALYSIS OF FLUIDS AND RELATED TOPICS: Turbulent solutions of fluid equations: Alexey Cheskidov, University of Illinois at Chicago

PACM Colloquium, Prof. Lin Lin, UC Berkeley University

Mon, Feb 6, 2023, 4:30 pm
Location: 214 Fine Hall

ANALYSIS OF FLUIDS AND RELATED TOPICS: Kevin Zumbrun, Indiana University

Thu, Feb 9, 2023, 3:00 pm
Location: Fine Hall 314