An Improved Lower Bound on Polynomial Multiplication

Mark R. Brown, David P. Dobkin

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


We prove an asymptotic lower bound of 3.52n nonscalar multiplications for (degree n — 1 by degree n-1) polynomialmultiplication in a model which allows only integers as scalars.

Original languageEnglish (US)
Pages (from-to)337-340
Number of pages4
JournalIEEE Transactions on Computers
Issue number5
StatePublished - May 1980

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


  • Algebraic complexity
  • lower bound
  • polynomial multiplication


Dive into the research topics of 'An Improved Lower Bound on Polynomial Multiplication'. Together they form a unique fingerprint.

Cite this