An Improved Lower Bound on Polynomial Multiplication

Mark R. Brown; David P. Dobkin

doi:10.1109/TC.1980.1675583

An Improved Lower Bound on Polynomial Multiplication

Mark R. Brown, David P. Dobkin

Research output: Contribution to journal › Article › peer-review

21 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 language	English (US)
Pages (from-to)	337-340
Number of pages	4
Journal	IEEE Transactions on Computers
Volume	C-29
Issue number	5
DOIs	https://doi.org/10.1109/TC.1980.1675583
State	Published - May 1980

All Science Journal Classification (ASJC) codes

Software
Theoretical Computer Science
Hardware and Architecture
Computational Theory and Mathematics

Keywords

Algebraic complexity
lower bound
polynomial multiplication

Access to Document

10.1109/TC.1980.1675583

Cite this

@article{caae6bbc9f414ef8adb6aa07af02d111,

title = "An Improved Lower Bound on Polynomial Multiplication",

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.",

keywords = "Algebraic complexity, lower bound, polynomial multiplication",

author = "Brown, \{Mark R.\} and Dobkin, \{David P.\}",

year = "1980",

month = may,

doi = "10.1109/TC.1980.1675583",

language = "English (US)",

volume = "C-29",

pages = "337--340",

journal = "IEEE Transactions on Computers",

issn = "0018-9340",

publisher = "IEEE Computer Society",

number = "5",

}

TY - JOUR

T1 - An Improved Lower Bound on Polynomial Multiplication

AU - Brown, Mark R.

AU - Dobkin, David P.

PY - 1980/5

Y1 - 1980/5

N2 - 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.

AB - 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.

KW - Algebraic complexity

KW - lower bound

KW - polynomial multiplication

UR - https://www.scopus.com/pages/publications/0019019882

UR - https://www.scopus.com/inward/citedby.url?scp=0019019882&partnerID=8YFLogxK

U2 - 10.1109/TC.1980.1675583

DO - 10.1109/TC.1980.1675583

M3 - Article

AN - SCOPUS:0019019882

SN - 0018-9340

VL - C-29

SP - 337

EP - 340

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 5

ER -

An Improved Lower Bound on Polynomial Multiplication

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this