Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > RANDOMIZED ALGEBRAIC DECISION TREES:
Reports tagged with Randomized Algebraic Decision Trees:
TR95-063 | 19th December 1995
Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky

#### A Lower Bound for Randomized Algebraic Decision Trees

We extend the lower bounds on the depth of algebraic decision trees
to the case of {\em randomized} algebraic decision trees (with
two-sided error) for languages being finite unions of hyperplanes
and the intersections of halfspaces, solving a long standing open
problem. As an application, among ... more >>>

TR99-020 | 9th June 1999
Marek Karpinski

#### Randomized Complexity of Linear Arrangements and Polyhedra

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