Homomorphism testing

Suresh asks, "Can we make use of the same BLR test to check whether a given mapping between two groups is a homomorphism or not?"

The answer is: Yes.

The question is: Let $G$ and $H$ be groups. A homomorphism between $G$ and $H$ (this is a definition from group theory) is a function $f : G \rightarrow H$ that satisfies $f(x \bullet y) = f(x) \cdot f(y)$ for all $x, y \in G$, where $\bullet$ denotes the group operation in $G$ and $\cdot$ denotes the group operation in $H$.

A natural question is, does the BLR test "work" for functions $f : G \to H$? I.e., if $f : G \rightarrow H$ is $\epsilon$-far from being a homomorphism (i.e., you need to change its values on $\epsilon |G|$ inputs to make it a true homomorphism), will the BLR test reject with probability $\Omega(\epsilon)$?

We showed the answer is yes, with rejection probability at least $\epsilon$, when $G = \mathbb{Z}_2^n$ and $H = \mathbb{Z}_2$.

The answer is still yes for any finite abelian groups $G$ and $H$. Possibly one could prove it with appropriately generalized Fourier analysis, but it's much easier to prove in this general case with pure combinatorics. This was originally proved by BLR for cyclic groups; later, Coppersmith gave a nice proof which also works for all abelian groups. See Section 4.1 of Rubinfeld's Testing Survey. Note that the constant factors necessarily get worse, because of examples like $G = H = \mathbb{Z}_9$, $f : 0, 3, 6, \mapsto 0; 1, 4, 7 \mapsto 1; 2, 5, 8 \mapsto -1$.

In fact, the BLR test still works even for nonabelian finite groups; this was claimed in BLR and then proved by Ben-Or, Coppersmith, L & R.