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 .