Michael Ben Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld

In this paper, we study two questions related to

the problem of testing whether a function is close to a homomorphism.

For two finite groups $G,H$ (not necessarily Abelian),

an arbitrary map $f:G \rightarrow H$, and a parameter $0 < \epsilon <1$,

say that $f$ is $\epsilon$-close to a homomorphism ...
more >>>

Scott Aaronson, Greg Kuperberg

This paper studies whether quantum proofs are more powerful than

classical proofs, or in complexity terms, whether QMA=QCMA. We prove

two results about this question. First, we give a "quantum oracle

separation" between QMA and QCMA. More concretely, we show that any

quantum algorithm needs order sqrt(2^n/(m+1)) queries to find ...
more >>>