Time-space tradeoffs for polynomial evaluation

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 exhibi...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Aldaz, M., Heintz, J., Matera, G., Montaña, J.L., Pardo, L.M.
Formato: JOUR
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_07644442_v327_n10_p907_Aldaz
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_07644442_v327_n10_p907_Aldaz
record_format dspace
spelling todo:paper_07644442_v327_n10_p907_Aldaz2023-10-03T15:39:38Z Time-space tradeoffs for polynomial evaluation Aldaz, M. Heintz, J. Matera, G. Montaña, J.L. Pardo, L.M. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_07644442_v327_n10_p907_Aldaz
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
description 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.
format JOUR
author Aldaz, M.
Heintz, J.
Matera, G.
Montaña, J.L.
Pardo, L.M.
spellingShingle Aldaz, M.
Heintz, J.
Matera, G.
Montaña, J.L.
Pardo, L.M.
Time-space tradeoffs for polynomial evaluation
author_facet Aldaz, M.
Heintz, J.
Matera, G.
Montaña, J.L.
Pardo, L.M.
author_sort Aldaz, M.
title Time-space tradeoffs for polynomial evaluation
title_short Time-space tradeoffs for polynomial evaluation
title_full Time-space tradeoffs for polynomial evaluation
title_fullStr Time-space tradeoffs for polynomial evaluation
title_full_unstemmed Time-space tradeoffs for polynomial evaluation
title_sort time-space tradeoffs for polynomial evaluation
url http://hdl.handle.net/20.500.12110/paper_07644442_v327_n10_p907_Aldaz
work_keys_str_mv AT aldazm timespacetradeoffsforpolynomialevaluation
AT heintzj timespacetradeoffsforpolynomialevaluation
AT materag timespacetradeoffsforpolynomialevaluation
AT montanajl timespacetradeoffsforpolynomialevaluation
AT pardolm timespacetradeoffsforpolynomialevaluation
_version_ 1807315465850060800

Ejemplares similares