Departmental Colloquium
Alexander Barvinok
University of Michigan
Computational complexity, zeros, and phase transition
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.
Friday November 11, 2022 at 3:00 PM in 636 SEO