Property Testing for Cyclic Groups and Beyond

Understand

This paper studies the problem of testing if an input (Gamma,*), where Gamma is a finite set of unknown size and * is a binary operation over Gamma given as an oracle, is close to a specified class of groups.

• Friedl et al.
• [Efficient testing of groups, STOC'05] have constructed an efficient tester using poly(log|Gamma|) queries for the class of abelian groups.
• We focus in this paper on subclasses of abelian groups, and show that these problems are much harder: Omega(|Gamma|^{1/6}) queries are necessary to test if the input is close to a cyclic group, and Omega(|Gamma|^c) queries for some constant c are necessary to test more generally if the input is close to an abelian group generated by k elements, for any fixed integer k>0.