Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1995 Copyright 1995 Universität Bonn, Institut für Informatik, Abt. V
85144

A Lower Bound for Randomized Algebraic Decision Trees
Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky
[Download PostScript] [Download PDF]

We extend the lower bounds on the depth of algebraic decision trees to the case of randomized algebraic decision trees (with two-sided error) for languages being finite unions of hyperplanes and the intersections of halfspaces. As an application, among other things, we derive, for the first time, $\Omega(n^2)$ randomized lower bound for the {\em knapsack problem} (which was previously only known for deterministic algebraic decision trees).

Last Change: 11/05/14 at 09:54:28
 English
Universität Bonn -> Institut für Informatik -> Abteilung V