Fast FPRAS for the Permanent

Abstract

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 for arbitrary nonnegative matrices, as in previous works. Jerrum, Sinclair, and Vigoda (2004) gave the first FPRAS for the permanent of a nonnegative matrix. The running time was subsequently improved to $\tilde{O}(n^7)$ by Bezáková, Štefankovič, Vazirani, and Vigoda (2008), and recently to $\tilde{O}(n^6)$ by Chen, Vigoda, and Yang (2026). We introduce a multicommodity-flow bound inspired by electrical flows, replacing the usual path-length factor by routing energy. For a boosted version of the classical JSV chain, we prove a relaxation-time bound of $O(n^3\log n)$ and show that stationary trajectories of this length estimate all stationary hole-pattern probabilities, yielding an $\tilde{O}(n^5)$-time FPRAS algorithm. Our new hole-weighted slide (HWS) chain improves both bounds to $O(n^2\log n)$, yielding an $\tilde{O}(n^4)$-time algorithm. Finally, we obtain the claimed $\tilde{O}(n^{3.5})$ running time by using a subset of $\tilde{O}(\sqrt{n})$ checkpoint temperatures in an iterated sequence of warm-starts to obtain initializations at every temperature.

44 pages