Additive estimates of the permanent using Gaussian fields

Abstract: We present a polynomial-time randomized algorithm for estimating the permanent of an arbitrary

M i m e s M

real matrix

A

up to an additive error. We do this by viewing the permanent of

A

as the expectation of a product of a centered joint Gaussian random variables whose covariance matrix we call the Gaussian embedding of

A

. The algorithm outputs the empirical mean

S_{N}

of this product after sampling from this multivariate distribution

N

times. In particular, after sampling

N

samples, our algorithm runs in time

O (M N)

with failure probability �egin{equation*} P(|S_{N}- ext{perm}(A)| > t) leq frac{3^{M}}{t^{2}N}alpha^{2M} end{equation*} for

a l p h a g e q | A |

.

This page was built for publication: Additive estimates of the permanent using Gaussian fields