DocumentCode :
2892246
Title :
Lower bounds for polynomial evaluation and interpolation problems
Author :
Shoup, Victor ; Smolensky, Roman
Author_Institution :
Dept. of Comput. Sci., Toronto Univ., Ont., Canada
fYear :
1991
fDate :
1-4 Oct 1991
Firstpage :
378
Lastpage :
383
Abstract :
It is shown that there is a set of points p1, p2,. . .,pn such that any algebraic program of depth d for polynomial evaluation (or interpolation) at these points has size Ω(n log n/log d). Moreover, if d is a constant, then a lower bound of Ω(n1+1/d) is obtained
Keywords :
interpolation; polynomials; symbol manipulation; algebraic program; interpolation problems; lower bound; polynomial evaluation; Arithmetic; Computer science; Costs; Discrete Fourier transforms; Ear; Interpolation; Polynomials;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on
Conference_Location :
San Juan
Print_ISBN :
0-8186-2445-0
Type :
conf
DOI :
10.1109/SFCS.1991.185394
Filename :
185394
Link To Document :
https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=2892246
بازگشت