Non‐Abelian homomorphism testing, and distributions close to their self‐convolutions
Michael Ben-Or, Don Coppersmith, Mike Luby, Ronitt Rubinfeld · Random Structures and Algorithms · 2007
Abstract In this paper, we study two questions related to the problem of testing whether a function is close to a homomorphism. For two finite groupsG,H(not necessarily Abelian), an arbitrary mapf:G,H, and a parameter 0 <ε< 1, say thatfisε‐close to a homomorphism if there is some homomorphismgsuch thatgandfdiffer on at mostε|G| elements ofG, and say thatfisε‐far otherwise. For a givenfandε, a homomorphism tester should distinguish whetherfis a homomorphism, or iffisε‐far from a homomorphism. WhenGis Abelian, it was known that the test which picksO(1/ε) random pairsx,yand tests thatf(x) +f(y) =f(x+y) gives a homomorphism tester. Our first result shows that such a test works for all groupsG. Next, we consider functions that are close to their self‐convolutions. LetA= {ag|gεG} be a distribution onG. The self‐convolution ofA,A′= {a |gεG}, is defined by It is known thatA=A′exactly whenAis the uniform distribution over a subgroup ofG. We show that there is a sense in which this characterization is robust—that is, ifAis close in statistical distance toA′, thenAmust be close to uniform over some subgroup ofG. Finally, we show a relationship between the question of testing whether a function is close to a homomorphism via the above test and the question of characterizing functions that are close to their self‐convolutions. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008