ECCC-Report TR04-052https://eccc.weizmann.ac.il/report/2004/052Comments and Revisions published for TR04-052en-usTue, 22 Jun 2004 09:06:03 +0300
Paper TR04-052
| Non-Abelian Homomorphism Testing, and Distributions Close to their Self-Convolutions |
Michael Ben Or,
Don Coppersmith,
Michael Luby,
Ronitt Rubinfeld
https://eccc.weizmann.ac.il/report/2004/052In 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$.
Tue, 22 Jun 2004 09:06:03 +0300https://eccc.weizmann.ac.il/report/2004/052