Lower bounds for polynomial evaluation and interpolation problems

Victor Shoup, Roman Smolensky

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherPubl by IEEE
Pages378-383
Number of pages6
ISBN (Print)0818624450
StatePublished - Dec 1991
EventProceedings of the 32nd Annual Symposium on Foundations of Computer Science - San Juan, PR, USA
Duration: Oct 1 1991Oct 4 1991

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

Other

OtherProceedings of the 32nd Annual Symposium on Foundations of Computer Science
CitySan Juan, PR, USA
Period10/1/9110/4/91

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Lower bounds for polynomial evaluation and interpolation problems'. Together they form a unique fingerprint.

Cite this