Verification of Identities
Sridhar Rajagopalan, Leonard J. Schulman · SIAM Journal on Computing · 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 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.