APPLICATIONS OF GAUSSIAN FIELDS TO THE PERMANENT AND THE MATCHING POLYNOMIAL

Abstract

In this thesis, we explore applications of Gaussian fields to the problems of approximating the permanent of a matrix and to the theory of the matching polynomial of a graph. In the first part of this thesis, we introduce a new randomized algorithm that leverages a form of Wick's theorem to estimate the permanent of a real matrix. In particular, we do this by viewing the permanent as the expectation of a product of centered joint Gaussian random variables with a particular covariance matrix C. The algorithm outputs the empirical mean S_{N} of this product after sampling N times. Our algorithm runs in polynomial time and we provide an error analysis to bound the failure probability. We compare our procedure to a previous procedure due to Gurvits. We discuss how to find a particular covariance matrix C using a semidefinite program and a relation to the Max-Cut problem and cut norms. In the second part of this thesis, we use these techniques to prove a new identity for the matching polynomial P_{G}(x) of a graph G. In doing so, we introduce a random procedure for estimating the coefficients of P_{G}(x) and provide a new proof of a duality result due to Godsil.