Lower bounds for polynomial evaluation and interpolation problems

Victor Shoup, Roman Smolensky

Research output: Contribution to journalArticlepeer-review


We show that there is a set of points p1, p2, . . . , pn such that any arithmetic circuit of depth d for polynomial evaluation (or interpolation) at these points has size Ω (n log n/log(2 + d/log n)). Moreover, for circuits of sub-logarithmic depth d, we obtain a lower bound of Ω(dn1+1/d) on its size.

Original languageEnglish (US)
Pages (from-to)301-311
Number of pages11
JournalComputational Complexity
Issue number4
StatePublished - 1996

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Mathematics
  • Computational Theory and Mathematics
  • Computational Mathematics


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

Cite this