Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Hyperplanes:
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 >>>

ISSN 1433-8092 | Imprint