Approximating the Permanent of a Random Matrix with Vanishing Mean

11/26/2017

∙

by   Lior Eldar, et al.

∙

0

∙

share

Building upon a recent approach pioneered by Barvinok [4, 5, 7, 8] we present a quasi-polynomial time algorithm for approximating the permanent of a typical n x n random matrix with unit variance and vanishing mean μ = (ln ln n)-1/6 to within inverse polynomial multiplicative error. This result counters the common intuition that the difficulty of computing the permanent, even approximately, stems merely from our inability to treat matrices with many opposing signs. We believe that our approach may have several implications to understanding the permanent in the context of computational complexity, anti-concentration statistics, and de-randomization.