51 citations · 141 across the 16 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2009★ 23 cited
Approximating the Permanent via Nonabelian Determinants
Cristopher Moore, Alexander Russell
Celebrated work of Jerrum, Sinclair, and Vigoda has established that the permanent of a {0,1} matrix can be approximated in randomized polynomial time by using a rapidly mixing Mar…
cs.CC2008
A simple constant-probability RP reduction from NP to Parity P
Cristopher Moore, Alexander Russell
The proof of Toda's celebrated theorem that the polynomial hierarchy is contained in $¶^{# P}$ relies on the fact that, under mild technical conditions on the complexity class ,…