An $\tilde{O}(n^3)$-time 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)$. Our algorithm extends to a strongly polynomial FPRAS for arbitrary nonnegative matrices with the same running-time bound (but in the unit-cost arithmetic model). 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 the classical JSV chain with perfect-matching weights multiplied by $n^2$, we prove a relaxation-time bound of $O(n^3\log n)$ and obtain comparable bounds for estimating the stationary probabilities of having a specified pair of unmatched vertices. We use a separate chain on assignments to generate a warm start at any given temperature, avoiding the long initialization of the JSV chain. Finally, we replace the JSV chain with a new chain that uses only $n$ hole weights and speeds up hole-weight learning by a factor of $n$.

arXiv comment62 pages