51 citations · 114 across the 12 of their papers we have counts for
Showing 2008Show all
2 papers · 1 filter
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 ,…
quant-ph2008
Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs
Hang Dinh, Alexander Russell
We study the problem of \emph{local search} on a graph. Given a real-valued black-box function f on the graph's vertices, this is the problem of determining a local minimum of f--a…