Reproduce “Faster FPRAS for the Permanent via Restricted Poincaré Inequalities and Coupled Flows” 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, Eric Vigoda, Xiongxin Yang

The authors improve an approximation algorithm for the permanent, which counts perfect matchings in a bipartite graph. They focus weight recalibration on the matching’s hole pattern—the unmatched vertices—rather than requiring rapid loss of memory across the whole Markov chain. A hole-restricted relaxation bound yields an O(n^6 ε^-2 log^5 n log(2/δ)) runtime, extending to nonnegative matrices; it does not show faster full-chain mixing.

Summary by alphaXiv.

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