An -time FPRAS for the PermanentResearch Paper
The permanent of an matrix is . For a 0/1 matrix it counts the perfect matchings of the bipartite graph whose adjacency matrix is . Valiant showed in 1979 that computing it exactly is #P-complete even for 0/1 matrices, so the question became how fast it…