We consider the following problem: Given an $n \times 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 $|A| = O(\sqrt{|G|})$.