Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > OHAD KLEIN:
All reports by Author Ohad Klein:

TR23-195 | 6th December 2023
Shai Evra, Shay Gadot, Ohad Klein, Ilan Komargodski

Verifying Groups in Linear Time

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




ISSN 1433-8092 | Imprint