Lower bounds for algebraic computation trees

ABSTRACT

A topological method is given for obtaining lower bounds for the height of algebraic computation trees, and algebraic decision trees. Using this method we are able to generalize, and present in a uniform and easy way, almost all the known nonlinear lower bounds for algebraic computations. Applying the method to decision trees we extend all the apparently known lower bounds for linear decision trees to bounded degree algebraic decision trees, thus answering the open questions raised by Steele and Yao [20]. We also show how this new method can be used to establish lower bounds on the complexity of constructions with ruler and compass in plane Euclidean geometry.

References

1. 1.W. Baur and V. Strassen, The complexity of partial derivatives. to appear (1982).
2. 2.A. Borodin and I. Munro, Computational complexity of algebraic and numeric problems. American Elsevier, 1975.
3. 3.D. Dobkin, A nonlinear lower bound on linear search tree programs for solving knapsack problems. JCSS 13, (1976) 69-73.
4. 4.D.P. Dobkin and R.J. Lipton, A lower bound of ½ n2 on linear search programs for the knapsack problem. JCSS 16, (1978) 413-417.
5. 5.D.P. Dobkin and R.J. Lipton, On the complexity of computations under varying sets of primitives. JCSS 18, (1979) 86-91.
6. 6.M.L. Fredman and B. Weide, On the complexity of computing the measure of &ugr;{ai, bi}. CACM 21, (1978) 540-544.
7. 7.D. Hilbert, Foundations of geometry, 1899. Edited and reprinted by Open Court, 1971.
8. 8.J.W. Jaromczyk, Lower bounds for problems defined by polynomial inequalities. Inter. FCT conference, Hungary, August 1981, F. Gecseg Ed. (Lecture Notes in Computer Science 117), Springer-Verlag, 165-172.
9. 9.J.W. Jaromczyk, An extension of Rabin's complete proof concept. Mathematical Foundations of Computer Science 1981, J. Gruska and M. Chytill Ed. (Lecture Notes in Computer Science 118), Springer-Verlag, 321-326.
10. 10.Lemoine, Géométrographie, 1907.
11. 11.J. Milnor, On the betti numbers of real algebraic varieties. Proc. AMS 15, (1964) 275-280.
12. 12.J. Milnor, Singular points of complex hypersurfces. Princeton Univ. Press, 1968.
13. 13.M.O. Rabin, Proving simultaneous positivity of linear forms. JCSS 6, (1972) 639-650.
14. 14.M.O. Rabin, unpublished lecture notes (1977).
15. 15.E.M. Reingold, On the optimality of some set algorithms. JACM 19, (1972) 649-659.
16. 16.A. Schmitt, On the computational power of the floor function. Info. Proc. Let. 14, (1982) 1-3.
17. 17.C.P. Schnorr, An extension of Strassen's degree bound. SIAM J. Comput. 10, (1981) 371-382.
18. 18.M.I. Shamos, Geometric complexity. Proc. 7th ACM STOC, Albuqueque, New Mexico, (May 1975) 224-233.
19. 19.M.I. Shamos, Problems in computational geometry, 1975.
20. 20.J.M. Steele and A.C. Yao, Lower bounds for algebraic decision trees. J. Algorithms 3, (1982) 1-8.
21. 21.V. Strassen, Die Berechnungskomplexität von elementarsymetrischen funktionen und von interpolationskoeffizienten. Numer. Math. 20, (1973) 238-251.
22. 22.V. Strassen, The computational complexity of continued fractions. Proc. of the 1981 ACM symposium on symbolic and algebraic computation, Utah, (August 1981) 51-67.
23. 23.R. Thom, Sur l'homologie des variétés algébriques réelles. Differential and Combinatorial Topology, Ed. S.S. Cairns, Princeton Univ. Press, 1965.
24. 24.A.C. Yao, On the complexity of comparison problems using linear functions. Proc. 16th STOC, Berkeley 1975, 85-89.
25. 25.A.C. Yao, A lower bound to finding convex hulls. Stanford Computer Science Report STAN-CS-79-733, (1979).
26. 26.A.C. Yao and R.L. Rivest, On the polyhedral decision problem. SIAM J. Comput. 9, (1980) 343-347.

Index Terms

• Computing methodologies

  • Machine learning

    • Machine learning approaches

      • Markov decision processes

• Mathematics of computing

  • Probability and statistics

    • Probabilistic representations

      • Decision diagrams

• Theory of computation

  • Computational complexity and cryptography

    • Complexity classes

    • Oracles and decision trees

  • Models of computation

    • Computability

      • Turing machines

  • Theory and algorithms for application domains

    • Machine learning theory

      • Markov decision processes

      • Reinforcement learning

        • Sequential decision making