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 >>>