{"ID":23507411,"CreatedAt":"2026-09-18T02:21:44.056544415Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.20717","arxiv_id":"2609.20717","title":"Fast FPRAS for the Permanent","abstract":"We give an FPRAS for the permanent of an $n\\times n$ $0/1$ matrix with running time $\\widetilde{O}(n^{3.5}\\varepsilon^{-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 $\\widetilde{O}(n^7)$ by Bezáková, Štefankovič, Vazirani, and Vigoda (2008), and recently to $\\widetilde{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 $\\widetilde O(n^5)$-time FPRAS algorithm. Our new hole-weighted slide (HWS) chain improves both bounds to $O(n^2\\log n)$, yielding an $\\widetilde O(n^4)$-time algorithm. Finally, we obtain the claimed $\\widetilde O(n^{3.5})$ running time by using a subset of $\\widetilde{O}(\\sqrt{n})$ checkpoint temperatures in an iterated sequence of warm-starts to obtain initializations at every temperature.","short_abstract":"We give an FPRAS for the permanent of an $n\\times n$ $0/1$ matrix with running time $\\widetilde{O}(n^{3.5}\\varepsilon^{-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 non...","url_abs":"https://arxiv.org/abs/2609.20717","url_pdf":"https://arxiv.org/pdf/2609.20717v1","authors":"[\"Xiaoyu Chen\",\"Heng Guo\",\"Eric Vigoda\",\"Xiongxin Yang\"]","published":"2026-09-17T17:14:13Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\",\"math.CO\",\"math.PR\"]","methods":"[]","has_code":false}