Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Lower bounds for algebraic computation trees with integer inputs
Yao A. (ed) SIAM Journal on Computing20 (4):655-668,1991.Type:Article
Date Reviewed: Jul 1 1992

The problem of deciding whether x ∈ Z n is a member of a scale-invariant and rationally dispersed W ∈ &RR; n has complexity &OHgr; ( log 2 β ( W ) - 2 n ) in the algebraic tree model, where β ( W ) is the number of connected components of W that are of positive measure. Working in this context, the author obtains tight lower bounds for a large class of problems, including element distinctness, set disjointedness, finding convex hull, integer max gap, and closest pair of a simple polygon.

Reviewer:  C. Calude Review #: CR115848
Bookmark and Share
 
Complexity Measures And Classes (F.1.3 )
 
 
Algebraic Algorithms (I.1.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Complexity Measures And Classes": Date
Nonuniform proof systems
Kämper J. Theoretical Computer Science 85(2): 305-331, 1991. Type: Article
Feb 1 1993
Reversal complexity
Chen J., Yap C. SIAM Journal on Computing 20(4): 622-638, 1991. Type: Article
Oct 1 1992
Handbook of theoretical computer science (vol. A)
van Leeuwen J., MIT Press, Cambridge, MA, 1990. Type: Book (9780444880710)
Sep 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy