Simons Collaboration on Algorithms and Geometry Monthly Meeting, December 2019

Alexander Barvinok
The interpolation method

I plan to discuss a relatively recent approach to approximate (deterministically) combinatorially defined polynomials (also known as partition functions), such as the permanent of a matrix, the independence polynomial of a graph (also known as the partition function in the hard core model), etc. The approach is based on an observation that a polynomial can be efficiently approximated in a complex domain, if it has no zeros in a slightly larger domain. In the first half of the talk, I plan to describe the (excruciatingly simple) general idea behind the method, while in the second half, I plan to describe some of the recent results, connections, directions and open questions.