Paper Info
Title
Lower Bounds on Algebraic Random Access Machines (Extended Abstract)
Abstract
We prove general lower bounds for set recognition on random access machines (RAMs) that operate on real numbers with algebraic operations {+, −, ×, /}, as well as RAMs that use the operations {+, −, ×, ⌈ ⌋}. We do it by extending a technique formerly used with respect to algebraic computation trees. In the case of algebraic computation trees, the complexity was related to the number of connected components of the set W to be recognized. For RAMs, two similar results apply to the number of connected components of Wo, the topological interior of W. Other results use (¯W)o, the interior of the topological closure of W.
Year
DOI
Venue
1995
10.1007/3-540-60084-1_88
ICALP
Keywords
Field
DocType
extended abstract,lower bounds,algebraic random access machines,connected component,lower bound
Discrete mathematics,Combinatorics,Algebraic number,Computer science,Random access
Conference
ISBN
Citations 
PageRank 
3-540-60084-1
0
0.34
References 
Authors
11
2
Name
Order
Citations
PageRank
Amir M Ben-Amram132730.52
Zvi Galil236341426.98