{"id":"arxiv/2608.26599","url":"https://arxiv.org/abs/2608.26599","tags":["cs.DM","cs.DS","math.PR"],"score":0,"title":"Faster FPRAS for the Permanent via Restricted Poincaré Inequalities and Coupled Flows","domain":"cs.DM","source":"arxiv","authors":["Xiaoyu Chen","Eric Vigoda","Xiongxin Yang"],"reviews":0,"subject":"cs.DM","summary":"The permanent of an $n\\times n$ $0/1$ matrix $A$ equals the number of perfect matchings in the bipartite graph with edges defined by $A$. Jerrum, Sinclair, and Vigoda (2004) presented an FPRAS for approximating the permanent of any nonnegative matrix using a novel simulated-annealing algorithm. The running time was improved by Bezáková, Štefankovič, Vazirani, and Vigoda (2008) to $O(n^7\\log^4 n)$ for $0/1$ matrices, for any fixed approximation and success parameters. We present the first asymptotic improvement over this running time bound, obtaining an $O(n^6\\log^5 n)$-time algorithm. As in…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-27","reactions":{}}