Additive estimates of the permanent using Gaussian fields

Abstract

We present a randomized algorithm for estimating the permanent of an $M\times M$ real matrix $A$ up to an additive error. We do this by viewing the permanent $\mathrm{perm}(A)$ of $A$ 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 total time $O(M^3+M^{2}N+MN)$ with failure probability \begin{equation*} P(|S_{N}-\text{perm}(A)| > t) \leq \frac{3^{M}}{t^{2}N} \prod^{2M}_{i=1} C_{ii}. \end{equation*} In particular, we can estimate $\mathrm{perm}(A)$ to an additive error of $\epsilon \left(\sqrt{3^{2M}{\prod }_{i=1}^{2M}{C}_{ii}}\right)$ in polynomial time. We compare to a previous procedure due to Gurvits. We discuss how to find a particular $C$ using a semidefinite program and a relation to the Max-Cut problem and cut-norms.

Added section 4, various corrections, and new introduction