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

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Matera, Guillermo
Publicado: 2000
Materias:
Pebble game; time-space tradeoff; straight-line program; elimination theory
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0885064X_v16_n1_p2_Aldaz
http://hdl.handle.net/20.500.12110/paper_0885064X_v16_n1_p2_Aldaz
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_0885064X_v16_n1_p2_Aldaz
record_format dspace
spelling paper:paper_0885064X_v16_n1_p2_Aldaz2023-06-08T15:46:34Z Time-Space Tradeoffs in Algebraic Complexity Theory Matera, Guillermo 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 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0885064X_v16_n1_p2_Aldaz 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)
topic Pebble game; time-space tradeoff; straight-line program; elimination theory
spellingShingle Pebble game; time-space tradeoff; straight-line program; elimination theory
Matera, Guillermo
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.
author Matera, Guillermo
author_facet Matera, Guillermo
author_sort Matera, Guillermo
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 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0885064X_v16_n1_p2_Aldaz
http://hdl.handle.net/20.500.12110/paper_0885064X_v16_n1_p2_Aldaz
work_keys_str_mv AT materaguillermo timespacetradeoffsinalgebraiccomplexitytheory
_version_ 1768542041445236736

Ejemplares similares