Additive estimates of the permanent using Gaussian fields

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{p}\mathrm{e}\mathrm{r}\mathrm{m}(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{p}\mathrm{e}\mathrm{r}\mathrm{m}(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.