Alexander Barvinok : Computational complexity, zeros, and phase transition

Posted by Marcus Michelen , part of the Departmental Colloquium.

At

Nov. 11, 2022, 3 p.m.

In

636 SEO

Abstract

On a few examples, such as the permanent of a matrix (partition function for a system of bosons), matching polynomial of a graph (partition function in a monomer-dimer system) and the independence polynomial of a graph (partition function in the hard core model), we illustrate how the computational complexity of approximation is related to complex zeros (even if we want to approximate in a real domain) and to the phase transition in the Lee - Yang sense. The idea is roughly as follows: a combinatorially defined multivariate polynomial can be efficiently approximated in a complex domain, if to does not have zeros in a slightly larger domain.