Lower Bounds on Complexity of Testing Membership to a Polygon for Algebraic and Randomized Decision Trees
| Title | Lower Bounds on Complexity of Testing Membership to a Polygon for Algebraic and Randomized Decision Trees |
| Publication Type | Technical Report |
| Year of Publication | 1993 |
| Authors | Grigoriev, D. Yu., & Karpinski M. |
| Other Numbers | 830 |
| Abstract | We describe a new method for proving lower bounds for algebraic decision trees. We prove, for the first time, that the minimum depth for arbitrary decision trees for the problem of testing the membership to a polygon with N nodes is ?(log N). Moreover, we prove that the corresponding lower bound for the randomized decision trees matches the above bound. Finally, we prove that for the algebraic exp-log decision trees (cf. [GSY 93]), the minimum depth is ?(?(log N)). We generalize the last result to the multidimensional case, showing that if an exp-log decision tree tests a membership to a semialgebraic set with a sum of Betti numbers M, then the depth of a tree is at least ?(?(log M)). |
| URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1993/tr-93-042.pdf |
| Bibliographic Notes | ICSI Technical Report TR-93-042 |
| Abbreviated Authors | D. Grigoriev and M. Karpinski |
| ICSI Publication Type | Technical Report |