Time-Space Tradeoffs in Algebraic Complexity Theory
We exhibit a new method for showing lower bounds for time-space tradeoffs of polynomial evaluation procedures given by straight-line programs. From the tradeoff results obtained by this method we deduce lower space bounds for polynomial evaluation procedures running in optimal nonscalar time. Time,...
Guardado en:
Autores principales: | , , , , |
---|---|
Formato: | Artículo publishedVersion |
Lenguaje: | Inglés |
Publicado: |
2000
|
Materias: | |
Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_0885064X_v16_n1_p2_Aldaz |
Aporte de: |
id |
paperaa:paper_0885064X_v16_n1_p2_Aldaz |
---|---|
record_format |
dspace |
spelling |
paperaa:paper_0885064X_v16_n1_p2_Aldaz2023-06-12T16:48:17Z Time-Space Tradeoffs in Algebraic Complexity Theory J. Complexity 2000;16(1):2-49 Aldaz, M. Heintz, J. Matera, G. Montaña, J.L. Pardo, L.M. Pebble game; time-space tradeoff; straight-line program; elimination theory We exhibit a new method for showing lower bounds for time-space tradeoffs of polynomial evaluation procedures given by straight-line programs. From the tradeoff results obtained by this method we deduce lower space bounds for polynomial evaluation procedures running in optimal nonscalar time. Time, denoted by L, is measured in terms of nonscalar arithmetic operations and space, denoted by S, is measured by the maximal number of pebbles (registers) used during the given evaluation procedure. The time-space tradeoff function considered in this paper is LS2. We show that for "almost all" univariate polynomials of degree at most d our time-space tradeoff functions satisfy the inequality LS2≥d8. From this we conclude that for "almost all" degree d univariate polynomials, any nonscalar time optimal evaluation procedure requires space at least S≥cd, where c>0 is a suitable universal constant. The main part of this paper is devoted to the exhibition of specific families of univariate polynomials which are "hard to compute" in the sense of time-space tradeoff (this means that our tradeoff function increases linearly in the degree). © 2000 Academic Press. Fil:Matera, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2000 info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion application/pdf eng info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_0885064X_v16_n1_p2_Aldaz |
institution |
Universidad de Buenos Aires |
institution_str |
I-28 |
repository_str |
R-134 |
collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
language |
Inglés |
orig_language_str_mv |
eng |
topic |
Pebble game; time-space tradeoff; straight-line program; elimination theory |
spellingShingle |
Pebble game; time-space tradeoff; straight-line program; elimination theory Aldaz, M. Heintz, J. Matera, G. Montaña, J.L. Pardo, L.M. Time-Space Tradeoffs in Algebraic Complexity Theory |
topic_facet |
Pebble game; time-space tradeoff; straight-line program; elimination theory |
description |
We exhibit a new method for showing lower bounds for time-space tradeoffs of polynomial evaluation procedures given by straight-line programs. From the tradeoff results obtained by this method we deduce lower space bounds for polynomial evaluation procedures running in optimal nonscalar time. Time, denoted by L, is measured in terms of nonscalar arithmetic operations and space, denoted by S, is measured by the maximal number of pebbles (registers) used during the given evaluation procedure. The time-space tradeoff function considered in this paper is LS2. We show that for "almost all" univariate polynomials of degree at most d our time-space tradeoff functions satisfy the inequality LS2≥d8. From this we conclude that for "almost all" degree d univariate polynomials, any nonscalar time optimal evaluation procedure requires space at least S≥cd, where c>0 is a suitable universal constant. The main part of this paper is devoted to the exhibition of specific families of univariate polynomials which are "hard to compute" in the sense of time-space tradeoff (this means that our tradeoff function increases linearly in the degree). © 2000 Academic Press. |
format |
Artículo Artículo publishedVersion |
author |
Aldaz, M. Heintz, J. Matera, G. Montaña, J.L. Pardo, L.M. |
author_facet |
Aldaz, M. Heintz, J. Matera, G. Montaña, J.L. Pardo, L.M. |
author_sort |
Aldaz, M. |
title |
Time-Space Tradeoffs in Algebraic Complexity Theory |
title_short |
Time-Space Tradeoffs in Algebraic Complexity Theory |
title_full |
Time-Space Tradeoffs in Algebraic Complexity Theory |
title_fullStr |
Time-Space Tradeoffs in Algebraic Complexity Theory |
title_full_unstemmed |
Time-Space Tradeoffs in Algebraic Complexity Theory |
title_sort |
time-space tradeoffs in algebraic complexity theory |
publishDate |
2000 |
url |
http://hdl.handle.net/20.500.12110/paper_0885064X_v16_n1_p2_Aldaz |
work_keys_str_mv |
AT aldazm timespacetradeoffsinalgebraiccomplexitytheory AT heintzj timespacetradeoffsinalgebraiccomplexitytheory AT materag timespacetradeoffsinalgebraiccomplexitytheory AT montanajl timespacetradeoffsinalgebraiccomplexitytheory AT pardolm timespacetradeoffsinalgebraiccomplexitytheory |
_version_ |
1769810123600953344 |