What is the fastest algorithm to check whether input table is a group?

Given an input table with binary operation $\circ$. I want to check whether given input table represents a group or not.

I need to verify the four axioms of a group.

1. The identity I can find it by just scanning the first row of the given table. -----$\mathcal{O}(|G|)$ running time.
2. Find the closure operation ie.e for any $x,y \in G$, I need to show that $x \circ y \in G$.------$\mathcal{O}(|G|^2)$
3. An inverse of an element.----$\mathcal{O}(|G|^2)$ Running time.
4. Associativity operation. -----$\mathcal{O}(|G|^3)$

Which gives me a $\mathcal{O}(|G|^3)$ running time algorithm to check whether the input table corresponds to some group.

Question : What is the fastest algorithm to check whether the input table is a group?

Model of computation is RAM, which computing $x \circ y$ takes constant time.

• Nice question! Computational group theory is the field (*baddum-tsh*) that covers this kind of thing. Sep 16 '18 at 9:14
• @DavidRicherby What's a better tagging? Does computer-algebra apply or should there be a new one?
– Raphael
Sep 16 '18 at 9:26
• @Raphael I'm not sure. To me, "computer algebra" seems to be more about what high school maths teachers call algebra (manipulating equations) rather than what mathematicians call algebra (group theory, linear algebra, etc.). But I don't have any real knowledge of the area. Sep 16 '18 at 9:29
• @Raphael A quick search for "group" suggests that we have plenty of questions about computing with groups, so a tag would probably be appropriate. Sep 16 '18 at 9:31
• $O(n^2)$ is the lower bound as you must check each $(x, y)$ combination for closure by an adversary argument (let the combination that you didn't check return a non-group element). So only associativity checking is where progress can be made.
– orlp
Sep 16 '18 at 9:46

There is a non-trivial randomized algorithm that can solve this in $O(n^2 \log (1/\delta))$ time, where $\delta>0$ is the desired error probability. See