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
Publicado: 1998
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_07644442_v327_n10_p907_Aldaz
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 paper:paper_07644442_v327_n10_p907_Aldaz
record_format dspace
spelling paper:paper_07644442_v327_n10_p907_Aldaz2023-06-08T15:45:43Z 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 exhibit specific families of univariate polynomials where this bound is reached. © Académie des Sciences/Elsevier, Paris. 1998 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_07644442_v327_n10_p907_Aldaz 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.
title Time-space tradeoffs for polynomial evaluation
spellingShingle 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
publishDate 1998
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_07644442_v327_n10_p907_Aldaz
http://hdl.handle.net/20.500.12110/paper_07644442_v327_n10_p907_Aldaz
_version_ 1768545055985893376

Ejemplares similares