Georgia Institute of Technology College of Sciences

Many hard problems of combinatorial counting can be encoded as problems of computing an appropriate partition function. Formally speaking, such a partition function is just a multivariate polynomial with great many monomials enumerating combinatorial structures of interest. For example, the permanent of an nxn matrix is a polynomial of degree n in n^2 variables with n! monomials enumerating perfect matchings in the complete bipartite graph on n+n vertices. Typically, we are interested to compute the value of such a polynomial at a real point; it turns out that to do it efficiently, it is very helpful to understand the behavior of complex zeros of the polynomial. This approach goes back to the Lee-Yang theory of the critical temperature and phase transition in statistical physics, but it is not identical to it: thinking of the phase transition from the algorithmic point of view allows us greater flexibility: roughly speaking, for computational purposes we can freely operate with “complex temperatures”. I plan to illustrate this approach on the problems of computing the permanent and its versions for non-bipartite graphs (hafnian) and hypergraphs, as well as for computing the graph homomorphism partition function and its versions (partition functions with multiplicities and tensor networks) that are responsible for a variety of problems on graphs involving colorings, independent sets, Hamiltonian cycles, etc. (This is the first (overview) lecture; two more will follow up on Thursday 1:30pm, Friday 3pm of the week. These two lectures are each 80 minutes' long.)