Abstract
By a "partition function" we understand a combinatorially defined polynomial, often multivariate and with many monomials, such as the permanent of a matrix. Under typical circumstances, it is not feasible to write it explicitly as a sum of monomials (because there are too many of them), although for every given monomial, some simple combinatorial rule quickly tells us whether it enters the polynomial and with what coefficient. We are interested in computing (approximating) such a polynomial efficiently at a given point. I will discuss an approach which allows one to do it, provided there are no complex zeros of the partition function in the vicinity of the point of interest. Examples include the already mentioned permanent, its higher-dimensional extensions, the matching polynomial of graphs and hypergraphs, the graph homomorphism and chromatic polynomial, as well as polynomials enumerating 0-1 solutions to sparse systems of linear equations. We will compare and contrast the approach with the Lee-Yang theory of phase transition in statistical physics and discuss its challenges.