CaltechAUTHORS
  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 http://resolver.caltech.edu/CaltechAUTHORS:20120208-152850561

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

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20120208-152850561

Abstract

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
http://dx.doi.org/10.1109/SFCS.1996.548520DOIUNSPECIFIED
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=548520&tag=1PublisherUNSPECIFIED
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.
Funders:
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:http://resolver.caltech.edu/CaltechAUTHORS:20120208-152850561
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: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=548520&isnumber=11790
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:29216
Collection:CaltechAUTHORS
Deposited By: Ruth Sustaita
Deposited On:09 Feb 2012 16:33
Last Modified:09 Feb 2012 16:33

Repository Staff Only: item control page