Abstract:
We exhibit a new method for showing lower bounds for the time complexity of polynomial evaluation procedures. Time, denoted by L, is measured in terms of nonscalar arithmetic operations. The time complexity function considered in this paper is L2. In contrast with known methods for proving lower complexity bounds, our method is purely combinatorial and does not require powerful tools from algebraic or diophantine geometry. By means of our method we are able to verify the computational hardness of new natural families of univariate polynomials for which this was impossible up to now. By computational hardness we mean that the complexity function L2 grows linearly in the degree of the polynomials of the family we are considering. Our method can also be applied to classical questions of transcendence proofs in number theory and geometry. A list of (old and new) formal power series is given whose transcendency can be shown easily by our method. © Springer-Verlag Berlin Heidelberg 1998.
Registro:
Documento: |
Artículo
|
Título: | Combinatorial hardness proofs for polynomial evaluation |
Autor: | Aldaz, M.; Heintz, J.; Matera, G.; Montaña, J.L.; Pardo, L.M. |
Ciudad: | Brno |
Filiación: | Universidad Publica de Navarra, Departamento de Matemática e Informática, 31006 Pamplona, Spain Universidad de Cantabria, Fac. de Ciencias, Depto. de Matemáticas, Est. y Comp., 39071 Santander, Spain Universidad de Buenos Aires, FCEyN, Departamento de Matemáticas, (1428) Buenos Aires, Argentina Universidad Nacional de Gral. Sarmiento, Instituto de Desarrollo Humano, (1663) San-Miguel, Argentina
|
Palabras clave: | Arithmetic operations; Complexity functions; Computational hardness; Formal power series; Lower bounds; Lower complexity; Polynomial evaluation; Time complexity; Arithmetic operations; Complexity functions; Computational hardness; Extended abstracts; Formal power series; Lower complexity; Polynomial evaluation; Time complexity; Computer science; Function evaluation; Number theory; Function evaluation; Number theory; Polynomials; Polynomials; Algebra |
Año: | 1998
|
Volumen: | 1450 LNCS
|
Página de inicio: | 167
|
Página de fin: | 175
|
Título revista: | 23rd International Symposium on the Mathematical Foundations of Computer Science, MFCS 1998
|
Título revista abreviado: | Lect. Notes Comput. Sci.
|
ISSN: | 03029743
|
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v1450LNCS_n_p167_Aldaz |
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 ----------
Aldaz, M., Heintz, J., Matera, G., Montaña, J.L. & Pardo, L.M.
(1998)
. Combinatorial hardness proofs for polynomial evaluation. 23rd International Symposium on the Mathematical Foundations of Computer Science, MFCS 1998, 1450 LNCS, 167-175.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v1450LNCS_n_p167_Aldaz [ ]
---------- CHICAGO ----------
Aldaz, M., Heintz, J., Matera, G., Montaña, J.L., Pardo, L.M.
"Combinatorial hardness proofs for polynomial evaluation"
. 23rd International Symposium on the Mathematical Foundations of Computer Science, MFCS 1998 1450 LNCS
(1998) : 167-175.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v1450LNCS_n_p167_Aldaz [ ]
---------- MLA ----------
Aldaz, M., Heintz, J., Matera, G., Montaña, J.L., Pardo, L.M.
"Combinatorial hardness proofs for polynomial evaluation"
. 23rd International Symposium on the Mathematical Foundations of Computer Science, MFCS 1998, vol. 1450 LNCS, 1998, pp. 167-175.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v1450LNCS_n_p167_Aldaz [ ]
---------- VANCOUVER ----------
Aldaz, M., Heintz, J., Matera, G., Montaña, J.L., Pardo, L.M. Combinatorial hardness proofs for polynomial evaluation. Lect. Notes Comput. Sci. 1998;1450 LNCS:167-175.
Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v1450LNCS_n_p167_Aldaz [ ]