Verification of Identities, S. Rajagopalan and L. J. Schulman. SIAM J. Computing, 29(4) 1155-1163, 2000.

We provide an $O(n^2 \log {1 \over \delta})$ time randomized algorithm to check whether a given operation $\circ :S \times S \rightarrow S$ is associative (where $n=|S|$ and $\delta>0$ is the error probability required of the algorithm.) We prove that (for any constant $\delta$) this performance is optimal up to a constant factor even in case the operation is cancellative''. No sub-$n^3$ time algorithm was previously known for this task.

More generally we give an $O(n^c)$ time randomized algorithm to check whether a collection of $c$-ary operations satisfy any given read-once'' identity.