Published October 1996
| public
Book Section - Chapter
Verifying Identities
- Creators
- Rajagopalan, Sridhar
-
Schulman, Leonard J.
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.
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
- Eprint ID
- 29216
- Resolver ID
- CaltechAUTHORS:20120208-152850561
- NSF
- CCR 91-19999
- Created
-
2012-02-09Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field
- Other Numbering System Name
- INSPEC Accession Number
- Other Numbering System Identifier
- 5444306