An Improved Lower Bound on Polynomial Multiplication

DOI10.1109/TC.1980.1675583MaRDI QIDQ3868771zbMATH OpenFDO

Authors Mark R. Brown, David P. Dobkin

Publication date 1980

Published in IEEE Transactions on Computers (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/TC.1980.1675583

zbMATH Keywords

algebraic complexityasymptotic lower boundnonscalar multiplicationspolynomial multiplication

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Theory of error-correcting codes and error-detecting codes (94B99)

Cited in

(9)

• Lower bounds in algebraic computational complexity
• A lower bound for polynomial multiplication
• Dense polynomial multiplication with reduced array manipulation overhead
• Multiplicative complexity of vector valued Boolean functions
• A lower bound on determinantal complexity
• Maximal bilinear complexity and codes
• On the tensor rank of multiplication in finite extensions of finite fields and related issues in algebraic geometry
• scientific article; zbMATH DE number 7758331 (Why is no real title available?)
• Lower bounds for additive complexity of linear operators and bilinear algorithms for matrix and polynomial multiplication over GF(2)

This page was built for publication: An Improved Lower Bound on Polynomial Multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3868771)