A Lower Bound for Randomized Algebraic Decision Trees
| Title | A Lower Bound for Randomized Algebraic Decision Trees |
| Publication Type | Technical Report |
| Year of Publication | 1995 |
| Authors | Grigoriev DYu., Karpinski M, der Heide FMeyer auf, Smolensky R |
| Other Numbers | 1008 |
| Keywords | Element Distinctness Problem, Faces, Hyperplanes, Knapsack Problem, Lower Bounds, Randomized Algebraic Decision Trees |
| Abstract | 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. |
| URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1995/tr-95-068.pdf |
| Bibliographic Notes | ICSI Technical Report TR-95-068 |
| Abbreviated Authors | D. Grigoriev, M. Karpinski, F. M. auf der Heide, and R. Smolensky |
| ICSI Publication Type | Technical Report |