You are not logged in to this journal. Log in

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 if 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.