Publication Details
Title: A Lower Bound for Randomized Algebraic Decision Trees
Author: D. Grigoriev, M. Karpinski, F. M. auf der Heide, and R. Smolensky
Group: ICSI Technical Reports
Date: December 1995
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1995/tr-95-068.pdf
Overview:
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, solving a long standing open problem. As an application, among other things, we derive, for the first time, an Omega(n^2) randomized lower bound for the Knapsack Problem which was previously only known for deterministic algebraic decision trees. It is worth noting that for the languages being finite unions of hyperplanes our proof method yields also a new elementary technique for deterministic algebraic decision trees without making use of Milnor's bound on Betti number of algebraic varieties. Keywords: Lower Bounds, Randomized Algebraic Decision Trees, Hyperplanes, Faces, Knapsack Problem, Element Distinctness Problem
Bibliographic Information:
ICSI Technical Report TR-95-068
Bibliographic Reference:
D. Grigoriev, M. Karpinski, F. M. auf der Heide, and R. Smolensky. A Lower Bound for Randomized Algebraic Decision Trees. ICSI Technical Report TR-95-068, December 1995
Author: D. Grigoriev, M. Karpinski, F. M. auf der Heide, and R. Smolensky
Group: ICSI Technical Reports
Date: December 1995
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1995/tr-95-068.pdf
Overview:
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, solving a long standing open problem. As an application, among other things, we derive, for the first time, an Omega(n^2) randomized lower bound for the Knapsack Problem which was previously only known for deterministic algebraic decision trees. It is worth noting that for the languages being finite unions of hyperplanes our proof method yields also a new elementary technique for deterministic algebraic decision trees without making use of Milnor's bound on Betti number of algebraic varieties. Keywords: Lower Bounds, Randomized Algebraic Decision Trees, Hyperplanes, Faces, Knapsack Problem, Element Distinctness Problem
Bibliographic Information:
ICSI Technical Report TR-95-068
Bibliographic Reference:
D. Grigoriev, M. Karpinski, F. M. auf der Heide, and R. Smolensky. A Lower Bound for Randomized Algebraic Decision Trees. ICSI Technical Report TR-95-068, December 1995