Verifying identities
Subramanian Rajagopalan, Leonard J. Schulman · 2002
The authors provide an O/spl tilde/(n/sup 2/) time randomized algorithm to check whether a given operation f:S/spl times/S/spl rarr/S is associative (letting n=|S|). They prove this performance is optimal (up to polylogarithmic factors) even in case the operation is "cancellative". No sub-n/sup 3/ algorithm was previously known for this task. More generally they give an O(n/sup c/) time randomized algorithm to check whether a collection of c-ary operations satisfy any given "read-once" identity.