An Improved Lower Bound on Polynomial Multiplication
- 1 May 1980
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-29 (5), 337-340
- https://doi.org/10.1109/tc.1980.1675583
Abstract
We prove an asymptotic lower bound of 3.52n nonscalar multiplications for (degree n – 1 by degree n – 1) polynomial multiplication in a model which allows only integers as scalars. Index Terms-Algebraic complexity, lower bound, polynomial multiplication.Keywords
This publication has 4 references indexed in Scilit:
- On the optimal evaluation of a set of bilinear formsLinear Algebra and its Applications, 1978
- New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalitiesIEEE Transactions on Information Theory, 1977
- Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear FormsSIAM Journal on Computing, 1973
- Class of constructive asymptotically good algebraic codesIEEE Transactions on Information Theory, 1972