Reproduce “An $\widetilde{O}(n^3)$-time FPRAS for the Permanent” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Xiaoyu Chen, Heng Guo, Eric Vigoda, Xiongxin Yang

The authors present a randomized algorithm for approximating the permanent of a nonnegative matrix, which counts perfect matchings in a weighted bipartite graph. It combines two-ended randomized routing, an assignment-based sampler, and fixed anchor reweighting to reduce work across simulated-annealing temperatures. For 0/1 inputs, it achieves an FPRAS in O(n³ε⁻² log⁶(n/ε)) arithmetic operations and comparisons, with success probability at least 3/4; this is a unit-cost theoretical bound, not a wall-clock claim.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.