|
University of Bonn -> Department of Computer Science -> Chair V | ||
CS-Reports 1996 | Copyright 1996 University of Bonn, Department of Computer Science, Abt. V | |
85149
|
Randomization and the Computational Power of Analytic and Algebraic Decision Trees
Dima Grigoriev, Marek Karpinski, Roman Smolensky [Download PostScript] [Download PDF] We introduce a new powerful method for proving {\it lower bounds} on {\it randomized} and {\it deterministic} analytic decision trees, and give direct applications of our results towards some concrete geometric problems. We design also {\it randomized} algebraic decision trees for recognizing the {\it positive octant} in $\run$ or computing MAX in $\R^{n+1}$ in depth $\log^{\bigO{}(1)}n$. Both problems are known to have linear lower bounds for the depth of any deterministic analytic decision tree recognizing them. The main {\em new} (and {\em unifying}) proof idea of the paper is in the reduction technique of the signs of {\em testing} functions in a decision tree to the signs of their {\em leading terms} at the specially chosen points. This allows us to reduce the complexity of a {\em decision} tree to the complexity of a certain {\em boolean} circuit. |
|
Last Change:
11/05/14 at 09:59:40
Deutsch |
University of Bonn -> Department of Computer Science -> Chair V |