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...
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | JOUR |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_07644442_v327_n10_p907_Aldaz |
| Aporte de: |
| Sumario: | 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. |
|---|