Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 1996 | public
Book Section - Chapter

Verifying Identities


We provide an O˜(n^2) time randomized algorithm to check whether a given operation f:S×S→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^3 algorithm was previously known for this task. More generally they give an O(n^c ) time randomized algorithm to check whether a collection of c-ary operations satisfy any given "read-once" identity.

Additional Information

© 1996 IEEE. Date of Current Version: 06 August 2002. The author thanks the NSF for funding DIMACS via NSF grant CCR 91-19999 which supported his stay at DIMACS. We wish to acknowledge helpful conversations with Manuel Blum, Michaelangelo Grigni, Sampath Kannan and Thomas Wilke. We also wish to thank Kousha Etessami for first bringing the question to our attention.

Additional details

August 19, 2023
October 24, 2023