ISSN:
1420-8954

Keywords:
Computational Complexity
;
Randomized Algebraic Decision Trees
;
Knapsack
;
Element Distinctness
;
Integer Programming
;
68Q15
;
68Q25
;
68Q40

Source:
Springer Online Journal Archives 1860-2000

Topics:
Computer Science

Notes:
Abstract We prove the firstnontrivial (andsuperlinear) lower bounds on the depth ofrandomized algebraic decision trees (with two-sided error) for problems being finite unions of hyperplanes and intersections of halfspaces, solving a long standing open problem. As an application, among other things, we derive, for the first time, an Ω(n 2)randomized lower bound for theKnapsack Problem, and an Ω(n logn)randomized lower bound for theElement Distinctness Problem which were previously known only 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 lower bound technique for deterministic algebraic decision trees without making use of Milnor's bound on Betti number of algebraic varieties.

Type of Medium:
Electronic Resource

Permalink