Complexity of testing if a binary operation is a group

Question

Given a binary operation specified as an $n \times n$ Cayley table, what is the complexity of the best deterministic algorithm for testing if the binary operation is a group?

There's a fairly simple deterministic $O(n^2 \log n)$ algorithm which works as follows. We can check if the binary operation is a quasigroup in $O(n^2)$ time by verifying the Latin square property. It is also easy to determine if the group has an identity element in $O(n^2)$ time. Quasigroups have generating sets of size at most $\log_2 n$ and such a generating set can be found in $O(n^2)$ time using a simple greedy algorithm. Applying Light's associativity test then allows us to test associativity in $O(n^2 \log n)$ time.

An obvious lower bound is $\Omega(n^2)$. According to wikipedia, there is a randomized BPP algorithm for testing associativity in $O(n^2)$, so this bound is tight for BPP algorithms.

Is there a deterministic $O(n^2)$ algorithm as well?

Answer 1

It was shown only recently that testing whether a Latin Square is a group takes time $O(n^{2} \log^{c} n) = \tilde{O}(n^2)$ (the $\tilde{O}$ hides the polylogarithmic factor).

https://arxiv.org/pdf/2011.03133.pdf