Lower bounds for arithmetic networks

1. Aho, A., Hopcroft, J., Ullman J.: The Design and Analysis of Computer Algorithms. Toronto: Addison-Wesley 1976

   Google Scholar 

2. Ben-Or, M.: Lower bounds for algebraic computation trees. A.C.M. 15^th Symp Theory Comput., pp. 80–86 (1983)

3. Benedetti, R., Risler, J. J.: Real algebraic and semialgebraic sets. Paris: Hermann 1990

   Google Scholar 

4. Blum, L., Shub, M., Smale S.: On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bull. Am. Math. Soc.21(1), 1–46 (1989)

   Google Scholar 

5. Bochnak, J., Coste, M., Roy, M.-F.: Géométrie algébrique réelle. Ergebnisse der Math., 3. Folge, Bd. 12. Berlin Heidelberg New York: Springer 1987

   Google Scholar 

6. Cucker, F.: “P _ℝ ≠NC _ℝ”. To appear in J. of Complexity

7. Cucker, F., Montaña, J. L., Pardo, L. M.: Time Bounded Computations over the Reals. To appear in Int. J. Algebra Comp.

8. Cucker, F., Torrecillas, A.: Two P-complete problems in the theory of the reals. To appear in Proceedings of ICALP '91, Madrid, 1991

9. Davenport, J. H., Heintz, J.: Real quantifier elimination is doubly exponential. J. Symb Comput. Soc.5, 29–36, New York: Academic Press 1988

   Google Scholar 

10. Dobkin, D. P., Lipton, R. J.: A lower bound of 1/2n ² on linear search programs for solving the Knapsack problem. JCSS18, 86–91 (1976)

    Google Scholar 

11. Fitchas, N., Galligo, A., Morgenstern, A.: Algorithmes rapides en séquentiel et en parallele pour l'élimination de quantificateurs en géométrie élémentaire. Seminaire de Structures Algebriques Ordennes, Universite de Paris VII, 1987

12. Von zur Gathen, J.: Parallel arithmetic computations: a survey. Mathematical Foundations on computer Science, 13th Proc. MFCS, 1986

13. Von zur Gathen, J.: Algebraic Complexity Theory. Technical Report of the Department of Computer Science. University of Toronto, 1988

14. Grigor'ev, D.: Complexity of deciding Tarski algebra. J. Symb. Comp.5, 65–108 (1988)

    Google Scholar 

15. Grigorev, D.: Lower bounds in algebraic computational complexity. J. Sov. Math.,4, 1388–1425 (1985)

    Google Scholar 

16. Heintz, J.: Definability and fast quantifier elimination over algebraically closed fields. Theor. Comp. Sci.24, 239–278 (1983). CORRIGENDUM in Theor. Comp. Science39, 343 (1985)

    Google Scholar 

17. Heintz, J. Roy, M.-F., Solerno, P.: Sur la Complexité du Principe de Tarski-Seidenberg. Bull. Soc. Math. France118, 101–126 (1990)

    Google Scholar 

18. Kung, H. T.: New algorithms and lower bounds for the parallel evaluation of certain rational expressions and recurrences. J. ACM23, 534–543 (1976)

    Google Scholar 

19. Meyer auf der Heide F.: On genuinely time bounded computations. Symp. Theor. Aspects Comp. LNCS349, 1–16, Berlin Heidelberg New York: Springer 1989

    Google Scholar 

20. Meyer auf der Heide, F.: A Polynomial Linear Search Algorithm for then-dimensional Knapsack Problem. J. ACM,31(3), 668–676 (1984)

    Google Scholar 

21. Milnor, J.: On the Betti numbers of real algebraic varieties. Proc. AMS15, 275–280 (1964)

    Google Scholar 

22. Montaña, J. L., Pardo, L. M., Recio, T.: The non-scalar model of complexity in computational geometry. Proc. of MEGA '90, Progress in Math. 94. Basel Birkhäuser, pp. 347–362 (1991)

    Google Scholar 

23. Montaña, J. L.: Cotas inferiores en teoría de la complejidad algebraica. Doctoral Thesis. Universidad de Cantabria, 1992

24. Pardo, L. M., Recio, T.: Arboles algebraicos: un modelo de computación en geometria. Contribuciones Cientificas, pp. 241–248, Universidad de Cantabria, 1988

25. Rabin, M.: Proving simultaneous positivity of linear forms. J. Comp. Syst. Sci.,6, 639–650 (1972)

    Google Scholar 

26. Smale, S.: On the topology of algorithms, I, J. Complexity,3, 81–89 (1987)

    Google Scholar 

27. Strassen, V.: Algebraic Complexity Theory. Hand Book of Theoretical Computer Science, capitulo11, 634–671 (1990)

    Google Scholar 

Download references