An Õ(n^3)-time FPRAS for the Permanent

Abstract

We give an FPRAS for the permanent of an n× n 0/1 matrix with running time Õ(n³). 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 Õ(n⁷) by Bezáková, Štefankovič, Vazirani, and Vigoda (2008), and recently to Õ(n⁶) 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², we prove a relaxation-time bound of O(n³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.

Subexponential Approximation of the Permanent in Deterministic Polynomial Time
Sergei Kudria, Jason Luo, Mahbod Majid
arXiv9 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
An FPRAS for Mixed Volumes
Xiaoyu Chen, Kuikui Liu
arXiv1 Nov 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematics ProbabilityarXiv
A simplified proof of the FPRAS for counting perfect matchings
Chenghua Liu, Boning Meng
arXiv19 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
An FPRAS for Counting Common Bases of Two Matroids
Xiaoyu Chen, Kuikui Liu
arXiv5 Oct 2026PreprintCC BY 4.0Full textProbabilityarXiv
A deterministic (1+ε)ⁿ approximation for the permanent of a nonnegative matrix
Dingding Dong, Vishesh Jain
arXiv10 Sep 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{chen2026on3time,
  title = {{An $\widetildeO(n^3)$-time FPRAS for the Permanent}},
  author = {Xiaoyu Chen and Heng Guo and Eric Vigoda and Xiongxin Yang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.20717},
  eprint = {2609.20717},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.20717},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - An Õ(n^3)-time FPRAS for the Permanent
AU  - Xiaoyu Chen
AU  - Heng Guo
AU  - Eric Vigoda
AU  - Xiongxin Yang
PY  - 2026
DA  - 2026/10/16
PB  - arXiv
DO  - 10.48550/arxiv.2609.20717
UR  - https://arxiv.org/abs/2609.20717
AB  - We give an FPRAS for the permanent of an n× n 0/1 matrix with running time 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 Õ(n^7) by Bezáková, Štefankovič, Vazirani, and Vigoda (2008), and recently to 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^3log 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.
ER  -

An Õ(n³)-time FPRAS for the Permanent

Abstract

Related

Cite