Name
Abstract | ||
|---|---|---|
We consider the role of randomness for the decisional complexity in algebraic decision (or computation) trees, i.e., the number of comparisons ignoring all other computation. Recently Ting and Yao showed that the problem of finding the maximum of n elements has decisional complexity O (log2 n) (1994, Inform. Process. Lett., 49, 39-43). In contrast, Rabin showed in 1972 an &Ohgr;(n) bound for the deterministic case (1972, J. Comput. System Sci., 6, 639-650). We point out that their technique is applicable to several problems for which corresponding &Ohgr;(n) lower bounds hold. We show that in general the randomized decisional complexity is logarithmic in the size of the decision tree. We then turn to the question of the number of random bits needed to obtain the Ting and Yao result. We provide a deterministic O (k log n) algorithm for finding the elements which are larger than a given element, given a bound k on the number of these elements. We use this algorithm to obtain an O (log2 n) random bits and O (log2 n) queries algorithm for finding the maximum. Copyright 2001 Academic Press. |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1006/inco.2000.3012 | Information and Computation/information and Control |
Keywords | DocType | Volume |
decisional complexity,yao result,log2 n,randomized decisional complexity,queries algorithm,random bit,k log n,deterministic o,n element,algebraic decision,decision tree,information processing,lower bound | Conference | 167 |
Issue | ISSN | Citations |
1 | Information and Computation | 0 |
PageRank | References | Authors |
0.34 | 28 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Moni Naor | 1 | 12948 | 1311.21 |
| Sitvanit Ruah | 2 | 293 | 13.04 |