Time-Space Tradeoffs in Algebraic Complexity Theory

Mostrar todas las versiones(3)

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

Detalles Bibliográficos
Autores principales: Aldaz, M., Heintz, J., Matera, G., Montaña, J.L., Pardo, L.M.
Formato: JOUR
Materias:
Pebble game; time-space tradeoff; straight-line program; elimination theory
Acceso en línea: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

Ejemplares similares

Ejemplares similares