Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR04-052 | 14th June 2004 00:00

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


Authors: Michael Ben Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld
Publication: 22nd June 2004 09:06
Downloads: 3620


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 if there is
some homomorphism $g$ such that $g$ and
$f$ differ on at most $\epsilon |G|$ elements of $G$, and say
that $f$ is $\epsilon$-far otherwise.
For a given $f$ and $\epsilon$,
a homomorphism tester should distinguish whether $f$ is
a homomorphism, or if $f$ is $\epsilon$-far from a homomorphism.
When $G$ is Abelian, it was known that the test which
picks $O(1/\epsilon)$ random pairs $x,y$
and tests that $f(x)+f(y)=f(x+y)$ gives a homomorphism tester.
Our first result shows that such a test works for
all groups $G$.

Next, we consider functions that are close to their self-convolutions.
Let $A = \{ a_g | g \in G\}$ be a distribution on $G$.
The self-convolution of $A$, $\cA = \{ \ca_g | g \in G\}$, is defined by
$\ca_x = \sum_{y,z \in G; yz=x}a_y a_z$.
It is known that
$A=\cA$ exactly when $A$ is the uniform distribution
over a subgroup of $G$.
We show that there is a sense in which this characterization is robust --
that is, if $A$ is close in statistical distance to $\cA$,
then $A$ must be close to uniform over some subgroup of $G$.

ISSN 1433-8092 | Imprint