TY - GEN
T1 - Lower bounds for polynomial evaluation and interpolation problems
AU - Shoup, Victor
AU - Smolensky, Roman
PY - 1991/12
Y1 - 1991/12
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0026387625&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0026387625&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:0026387625
SN - 0818624450
T3 - Annual Symposium on Foundations of Computer Science (Proceedings)
SP - 378
EP - 383
BT - Annual Symposium on Foundations of Computer Science (Proceedings)
PB - Publ by IEEE
T2 - Proceedings of the 32nd Annual Symposium on Foundations of Computer Science
Y2 - 1 October 1991 through 4 October 1991
ER -