A Caltech Library Service

Verifying Identities

Rajagopalan, Sridhar and Schulman, Leonard J. (1996) Verifying Identities. In: Proceedings: 37th Annual Symposium on Foundations of Computer Science. IEEE Computer Society , Los Alamitos, CA, pp. 612-616. ISBN 0-8186-7594-2

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
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.
Funding AgencyGrant Number
NSFCCR 91-19999
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number5444306
Record Number:CaltechAUTHORS:20120208-152850561
Persistent URL:
Official Citation:Rajagopalan, S.; Schulman, L.J.; , "Verifying identities," Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on , vol., no., pp.612-616, 14-16 Oct 1996 doi: 10.1109/SFCS.1996.548520 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:29216
Deposited By: Ruth Sustaita
Deposited On:09 Feb 2012 16:33
Last Modified:09 Feb 2012 16:33

Repository Staff Only: item control page