The ACO Seminar (2019–2020)

I plan to discuss a relatively recent approach to efficiently compute (approximate) big combinatorially defined polynomials (known to physicists as partition functions), such as the permanent of a matrix, the matching and the independence polynomials of a graph, etc. The method is based on an observation that a multivariate polynomial can be efficiently approximated in a complex domain, provided it does not have zeros in a slightly larger domain. Time permitting, connections with the Lee-Yang Theory of phase transition will be discussed.

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.