Dima Grigoriev, Marek Karpinski, A. C. Yao

We prove an exponential lower bound on the size of any

fixed-degree algebraic decision tree for solving MAX, the

problem of finding the maximum of $n$ real numbers. This

complements the $n-1$ lower bound of Rabin \cite{R72} on

the depth of ...
more >>>

Marek Karpinski

We survey some of the recent results on the complexity of recognizing

n-dimensional linear arrangements and convex polyhedra by randomized

algebraic decision trees. We give also a number of concrete applications

of these results. In particular, we derive first nontrivial, in fact

quadratic, ...
more >>>