Metraipolis › archive › dc_9dd7217de320
Fast FPRAS for the Permanent — arXiv:2609.20717
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.20717
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-10T04:26:04.004Z
- SHA-256 of the archived text
ac762f1d79775f77bbc82c5df3dfbcfbf54744e01805e4d784d1dba3024ce79c- Stable URL of this page
https://metraipolis.com/documento/dc_9dd7217de320
How to cite
Fast FPRAS for the Permanent — arXiv:2609.20717 — arXiv (en), https://arxiv.org/abs/2609.20717 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9dd7217de320 (Metraipolis archive dc_9dd7217de320, sha256 ac762f1d79775f77bbc82c5df3dfbcfbf54744e01805e4d784d1dba3024ce79c)
BibTeX
@misc{dc9dd7217de320,
title = {Fast FPRAS for the Permanent — arXiv:2609.20717},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.20717},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9dd7217de320; sha256 ac762f1d79775f77bbc82c5df3dfbcfbf54744e01805e4d784d1dba3024ce79c},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.20717. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-18 in math.PR).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Discrete Mathematics (cs.DM); Combinatorics (math.CO); Probability (math.PR).
Pagina del lavoro: https://arxiv.org/abs/2609.20717 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T04:09:58.372Z dalla pagina https://arxiv.org/catchup/math.PR/2026-09-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).