Registro:

Referencias:

• Aldaz, M., Heintz, J., Matera, G., Montana, J.L., Pardo, L.M., Time-space tradeoffs in algebraic complexity theory (1996) J. of Complexity, , (submitted to)
• Baur, W., Simplified lower bounds for polynomials with algebraic coefficients (1997) J. of Complexity, 13 (1), pp. 38-41
• Belaga, E.G., Some problems involved in the computations of polynomials (1958) Dokl. Akad. Nauk. SSSR, 123, pp. 775-777
• Bochnak, J., Coste, M., Roy, M.-F., Géométrie Algébrique Réelle (1987) Ergebnisse der Mathematik und Ihrer Grenzgebiete, 12. , 3. Folge Springer
• Borodin, A., Munro, I., (1975) The Computational Complexity of Algebraic and Numeric Problems, , American Elsevier
• Bürgisser, P., Clausen, M., Shokrollahi, A., Algebraic complexity theory (1997) A Series of Comprehensive Studies in Mathematics, 315. , Springer
• Fitchas, N., Galligo, A., Morgenstern, J., Precise sequential and parallel complexity bounds for the quantifier elimination over algebraically closed fields (1990) J. Pure Appl. Algebra, 67, pp. 1-14
• Von Zur Gathen, J., Algebraic complexity theory (1988) Ann. Review of Comp. Sci., 3, pp. 317-347
• Von Zur Gathen, J., Strassen, V., Some polynomials that are hard to compute (1980) Theoret. Comp. Sc., 11 (3), pp. 331-335
• Heintz, J., On the computational complexity of polynomials and bilinear mappings (1989) Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. Lectures Notes in Computer Science, 356, pp. 269-300. , A survey. L. Huget and A. Poli, editors Springer
• Heintz, J., Morgenstern, J., On the intrinsic complexity of elimination theory (1993) J. of Complexity, 9 (4), pp. 471-498
• Heintz, J., Schnorr, C.P., Testing polynomials which are easy to compute. Logic and algorithmic: An international symposium held in honor of ernst specker (1982) L'Enseignement de Mathématiques, 30, pp. 237-254. , Genève
• Heintz, J., Sieveking, M., Lower bounds for polynomials with algebraic coefficients (1980) Theoret. Comp. Sc., 11 (3), pp. 321-330
• Krick, T., Pardo, L.M., A computational method for diophantine approximation (1996) Algorithms in Algebraic Geometry and Applications. Proceedings of MEGA'94, Progress in Mathematics, 143, pp. 193-254. , L. González-Vega and T. Recio, editors Birkhäuser
• Kung, H.T., Traub, J.F., All algebraic functions can be computed fast (1978) J. of the ACM, 25 (2), pp. 245-260
• Motzkin, T.S., Evaluation of polynomials and evaluation of rational functions (1955) Bull. Amer. Math. Soc., 61, p. 163
• Pardo, L.M., How lower and upper complexity bounds meet in elimination theory (1995) Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. Proceedings AAECC-11, Lecture Notes in Computer Science, 948, pp. 33-69. , G. Cohen, M. Giusti and T. Mora, editors Springer
• Paterson, M.S., Stockmeyer, L.J., On the number of nonscalar multiplications necessary to evaluate polynomials (1973) SIAM J. of Computing, 2 (1), pp. 60-66
• Puddu, S., Sabia, J., An effective algorithm for quantifier elimination over algebraically closed fields using straight-line programs J. of Pure Appl. Algebra, , (to appear)
• Schnorr, C.P., Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials (1978) Theoret. Comp. Sc., 7 (3), pp. 251-261
• Shoup, V., Smolensky, R., Lower bounds for polynomial evaluation and interpolation problems (1991) Proceedings of the 32nd Annual Symposium FOCS, pp. 378-383. , IEEE Computer Society Press
• Stoss, H.J., On the representation of rational functions of bounded complexity (1989) Theoret. Comp. Sc., 64 (1), pp. 1-13
• Strassen, V., Polynomials with rational coefficients which are hard to compute (1974) SIAM J. of Computing, 3, pp. 128-149
• Strassen, V., Algebraic complexity theory (1990) Handbook of Theoretical Computer Science, A, pp. 635-672. , Chap. 11 Elsevier Science Publishers

Citas:

---------- APA ----------

---------- CHICAGO ----------

---------- MLA ----------

---------- VANCOUVER ----------