Verifying Groups in Linear Time

Consider the following problem: Given an$n$×$n$multiplication table, decide whether it is a Cayley multiplication table of a group. Among deterministic algorithms for this problem, the best known algorithm is implied by F. W. Light's associativity test (1949) and has running time of${O}(n^{2}\log n)$. Allowing randomization. the best known algorithm has running time of$O(n^{2}\log(1/\delta))$, where$\delta > 0$is the error probability of the algorithm (Rajagopalan and Schulman, FOCS 1996, SICOMP 2000). In this work, we improve upon both of the above known algorithms. Specifically, we present a deterministic algorithm for the above problem whose running time is$O(n^{2})$. This performance is optimal up to constants. A central tool we develop is an efficient algorithm for finding a subset$A$of a group$G$satisfying$A^{2}=G$while$\vert A\vert=O(\sqrt{\vert G\vert })$.