An $\widetilde{O}(n^3)$-time FPRAS for the Permanent

Xiaoyu Chen; Heng Guo; Eric Vigoda; Xiongxin Yang

An $\widetilde{O}(n^3)$-time FPRAS for the Permanent

Xiaoyu Chen, Heng Guo, Eric Vigoda, Xiongxin Yang

arXivarxiv/2609.20717Sep 17, 2026cs.DSscore 0

We give an FPRAS for the permanent of an $n\times n$ $0/1$ matrix with running time $\widetilde 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 $\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…

Source JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2609.20717
curl -X POST /api/v1/records/arxiv/2609.20717/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.20717/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'