Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > HOMOMORPHISM TESTING:
Reports tagged with homomorphism testing:
TR04-052 | 14th June 2004
Michael Ben Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld

#### Non-Abelian Homomorphism Testing, and Distributions Close to their Self-Convolutions

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 >>>

TR06-055 | 10th April 2006
Scott Aaronson, Greg Kuperberg

#### Quantum Versus Classical Proofs and Advice

This paper studies whether quantum proofs are more powerful than
classical proofs, or in complexity terms, whether QMA=QCMA. We prove
separation" between QMA and QCMA. More concretely, we show that any
quantum algorithm needs order sqrt(2^n/(m+1)) queries to find ... more >>>

ISSN 1433-8092 | Imprint