Artículo
Aldaz, M.; Heintz, J.; Matera, G.; Montaña, J.L.; Pardo, L.M. "Time-space tradeoffs for polynomial evaluation " (1998) Comptes Rendus de l'Academie des Sciences - Series I: Mathematics. 327(10):907-912
Estamos trabajando para incorporar este artículo al repositorio
Consulte la política de Acceso Abierto del editor
Abstract:
We develop a new method for showing lower bounds for the time-space tradeoff of polynomial evaluation procedures given by straight-line programs. By means of this method we prove an asymptotically sharp lower bound for the time-space tradeoff of general procedures of polynomial evaluation and exhibit specific families of univariate polynomials where this bound is reached. © Académie des Sciences/Elsevier, Paris.
Registro:
| Documento: | Artículo |
| Título: | Time-space tradeoffs for polynomial evaluation |
| Autor: | Aldaz, M.; Heintz, J.; Matera, G.; Montaña, J.L.; Pardo, L.M. |
| Filiación: | Depto. de Matematica e Informatica, University Pública de Navarra, E-31006 Pamplona, Spain Departamento de Matemáticas, Estadistica y Computación, Universidad de Cantabria, E-39071 Santander, Spain Departamento de Matemáticas, Universidad de Buenos Aires, Ciudad Universitaria, 1428 Buenos Aires, Argentina |
| Año: | 1998 |
| Volumen: | 327 |
| Número: | 10 |
| Página de inicio: | 907 |
| Página de fin: | 912 |
| Título revista: | Comptes Rendus de l'Academie des Sciences - Series I: Mathematics |
| Título revista abreviado: | C. R. Acad. Sci. Ser. I Math. |
| ISSN: | 07644442 |
| CODEN: | CASME |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_07644442_v327_n10_p907_Aldaz |
Referencias:
- Aldaz, M., (1997), Ph.D. Thesis (work in progress), Public University of Navarra; Borodin, A., Time-space tradeoffs (getting closer to the barrier?) (1993) Lect. Notes Coraput. Sci., 762, pp. 209-220. , Proc. of the 4th ACM-SIGSAM Int. Symp. ISAAC'93, Springer
- Heintz, J., Morgenstern, J., On the intrinsic complexity of elimination theory (1993) J. of Complexity, 9, pp. 471-498
- Heintz, J., Sieveking, M., Lower bounds for polynomials with algebraic coefficients (1980) Theoret. Comput Sci., 11, pp. 321-330
- Krick, T., Pardo, L.M., A computational method for diophantine approximation (1996) Progress in Math., 143, pp. 193-254. , Birkhäuser Verlag
- Paterson, M.S., Stockmeyer, L.J., On the number of nonscalar multiplications necessary to evaluate polynomials (1973) SIAM J. Comput., 2 (1), pp. 60-66
- Strassen, V., Polynomials with rational coefficients which are hard to compute (1974) SIAM J. Comput., 3, pp. 128-149
Citas:
---------- APA ----------
Aldaz, M., Heintz, J., Matera, G., Montaña, J.L. & Pardo, L.M. (1998) . Time-space tradeoffs for polynomial evaluation . Comptes Rendus de l'Academie des Sciences - Series I: Mathematics, 327(10), 907-912.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_07644442_v327_n10_p907_Aldaz [ ]
---------- CHICAGO ----------
Aldaz, M., Heintz, J., Matera, G., Montaña, J.L., Pardo, L.M. "Time-space tradeoffs for polynomial evaluation " . Comptes Rendus de l'Academie des Sciences - Series I: Mathematics 327, no. 10 (1998) : 907-912.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_07644442_v327_n10_p907_Aldaz [ ]
---------- MLA ----------
Aldaz, M., Heintz, J., Matera, G., Montaña, J.L., Pardo, L.M. "Time-space tradeoffs for polynomial evaluation " . Comptes Rendus de l'Academie des Sciences - Series I: Mathematics, vol. 327, no. 10, 1998, pp. 907-912.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_07644442_v327_n10_p907_Aldaz [ ]
---------- VANCOUVER ----------
Aldaz, M., Heintz, J., Matera, G., Montaña, J.L., Pardo, L.M. Time-space tradeoffs for polynomial evaluation . C. R. Acad. Sci. Ser. I Math. 1998;327(10):907-912.Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_07644442_v327_n10_p907_Aldaz [ ]
