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

By: Michael Ben Or; Don Coppersmith; Mike Luby; Ronnitt Rubinfeld

Published in: RC23465 in 2004


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .