Fast FPRAS for the Permanent

Xiaoyu Chen, Heng Guo, Eric Vigoda +1

We give an FPRAS for the permanent of an $n\times n$ $0/1$ matrix with running time $\tilde{O}(n^{3.5}{\epsilon }^{-2})$. Our algorithm extends to a strongly polynomial FPRAS f…