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 and a parameter , say that f is -close to a homomorphism if there is some homomorphism g such that g and f differ on at most |G| elements of G, and say that f is -far otherwise. For a given f and , a homomorphism tester should distinguish whether f is a homomorphism, or if f is -far from a homomorphism. When G is Abelian, it was known that the test which picks 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 = be a distribution on G. The self-convolution of A, A' = , is defined by a'_x = It is known that A = A' 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 A', then A must be close to uniform over some subgroup of G. ¹