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

Guardado en:
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