Loading...
APPLICATIONS OF GAUSSIAN FIELDS TO THE PERMANENT AND THE MATCHING POLYNOMIAL
Mukerji, Tantrik
Mukerji, Tantrik
Citations
Altmetric:
Genre
Thesis/Dissertation
Date
2024-08
Advisor
Committee member
Group
Department
Mathematics
Subject
Permanent link to this record
Collections
Research Projects
Organizational Units
Journal Issue
DOI
http://dx.doi.org/10.34944/dspace/10584
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.
Description
Citation
Citation to related work
Has part
ADA compliance
For Americans with Disabilities Act (ADA) accommodation, including help with reading this content, please contact scholarshare@temple.edu