
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 1993  Copyright 1993 Universität Bonn, Institut für Informatik, Abt. V  
8599

Lower Bounds on Complexity of Testing Membership to a Polygon for Algebraic and Randomized Computation Trees
Dima Grigoriev, Marek Karpinski [Download PostScript] [Download PDF] We describe a new method for proving lower bounds for algebraic computation trees. We prove, for the first time, that the minimum depth for arbitrary computation trees for the problem of testing the membership to a polygon with $N$ nodes is $\Omega(\log N)$. Moreover, we prove that the corresponding lower bound for the randomized computation trees matches the above bound. Finally, we prove that for the algebraic explog computation trees (cf. [GSY 93]), the minimum depth is $\Omega(\sqrt{\,\log N})$. We generalize the last result to the multidimensional case, showing that if an explog computation tree tests a membership to a semialgebraic set with a sum of Betti numbers $M$, then the depth of a tree is at least $\Omega(\sqrt{\,\log M})$ 

Last Change:
11/20/08 at 15:07:01
English 
Universität Bonn > Institut für Informatik > Abteilung V 