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