2.2k citations · 2.6k across the 20 of their papers we have counts for
Showing cs.CCShow all
3 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 ,…
cs.CC2005
The Phase Transition in Exact Cover
Vamsi Kalapala, Cris Moore
We study EC3, a variant of Exact Cover which is equivalent to Positive 1-in-3 SAT. Random instances of EC3 were recently used as benchmarks for simulations of an adiabatic quantum…