** **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

By:* Michael Ben-Or, Don Coppersmith, Mike Luby, Ronitt Rubinfeld*

Published in: Lecture Notes in Computer Science, volume 3122, (no ), pages 273-85 in 2004

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .