Efficient testing of groups

We construct an efficient probabilistic algorithm that, given a finite set with a binary operation, tests if it is an abelian group. The distance used is an analogue of the edit distance for strings. The query complexity of the tester is polylogarithmic in the size of the set. Previous testers used Hamming type distances and had superlinear query complexity. A building block for our construction is a constant query complexity homomorphism tester for functions mapping an given finite group into an arbitrary set equipped with a binary operation.

Authors

• Katalin Friedl
• Gábor Ivanyos
• Miklos Santha

Keywords

• edit distance
• group multiplication testing
• probabilistic computation
• quantum computation