An Improved Lower Bound on Polynomial Multiplication

Mark R. Brown, David P. Dobkin

Research output: Contribution to journalArticle

17 Scopus citations

Abstract

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
VolumeC-29
Issue number5
DOIs
StatePublished - May 1980
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Keywords

  • Algebraic complexity
  • lower bound
  • polynomial multiplication

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

Cite this