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, randomized lower bounds on the problems like Knapsack and
Bounded Integer Programming.
We formulate further several open problems and possible directions
for future research.