Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > MICHAEL BEN OR:
All reports by Author Michael Ben Or:

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




ISSN 1433-8092 | Imprint