Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR23-195 | 6th December 2023 16:44

Verifying Groups in Linear Time


Authors: Shai Evra, Shay Gadot, Ohad Klein, Ilan Komargodski
Publication: 6th December 2023 16:50
Downloads: 230


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|})$.

ISSN 1433-8092 | Imprint