A LOWER-BOUND FOR RANDOMIZED ALGEBRAIC DECISION TREES

We prove the first nontrivial (and superlinear) lower bounds on the de pth of randomized algebraic decision trees (with two-sided error) for problems being finite unions of hyperplanes and intersections of halfs paces, 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, and an Omega(n log n) randomize d lower bound for the Element Distinctness Problem which were previous ly known only for deterministic algebraic decision trees. It is worth noting that for the languages being finite unions of hyperplanes our p roof method yields also a new elementary lower bound technique for det erministic algebraic decision trees without making use of Milnor's bou nd on Betti number of algebraic varieties.