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: |
| |||||||||
| 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: |
| |||||||||
| Other Numbering System: |
| |||||||||
| 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: | 23 Aug 2016 10:09 |
Repository Staff Only: item control page
