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.


The identity I can find it by just scanning the first row of the given table. -----$\mathcal{O}(|G|)$ running time.
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)$
An inverse of an element.----$\mathcal{O}(|G|^2)$ Running time.
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.
There is a non-trivial randomized algorithm that can solve this in $O(n^2 \log (1/\delta))$ time, where $\delta&gt;0$ is the desired error probability.  See

Verification of Identities.  Sridhar Rajagopalan and Leonard J. Schulman.  SIAM Journal on Computing, 29(4), pp.1155-1163.