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 (not necessarily Ableian), an arbitrary map and a parameter say that to a homomorphism if there is some homomorphism such that and differ on at most elements of and say that
is otherwise. for a given and a homomorphism tester should distinguish whether is a homomorphism, or if is - far from a homomorphism. When is Abelian, it was known that the test which picks random pairs x, y and tests that gives a homomorphism tester. Our first result shows that such a test works for all groups . Next, we consider functions that are close to their self-convolutions. Let be a distribution on . The self-convolution of is defined by It is known that exactly when is the uniform distribution over a subgroup of We show that there is a sense in which this characterization is robust -- that is, if is close in statistical distance to then must be close to uniform over some subgroup of