Approximating Permanent of Random Matrices with Vanishing Mean: Made Better and Simpler

Understand

The algorithm and complexity of approximating the permanent of a matrix is an extensively studied topic.

• Recently, its connection with quantum supremacy and more specifically BosonSampling draws special attention to the average-case approximation problem of the permanent of random matrices with zero or small mean value for each entry.
• Eldar and Mehraban (FOCS 2018) gave a quasi-polynomial time algorithm for random matrices with mean at least $1/\mathbf{\mathrm{polyloglog}} (n)$.
• In this paper, we improve the result by designing a deterministic quasi-polynomial time algorithm and a PTAS for random matrices with mean at least $1/\mathbf{\mathrm{polylog}}(n)$.