TR04-052 Authors: Michael Ben Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld

Publication: 22nd June 2004 09:06

Downloads: 1493

Keywords:

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