An Improved Lower Bound on Polynomial Multiplication

DOI10.1109/TC.1980.1675583zbMath0431.68052MaRDI QIDQ3868771

Mark R. Brown, David P. Dobkin

Publication date: 1980

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

zbMATH Keywords

algebraic complexityasymptotic lower boundpolynomial multiplicationnonscalar multiplications

Mathematics Subject Classification ID

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

Related Items

A lower bound for polynomial multiplication, Maximal bilinear complexity and codes, Multiplicative complexity of vector valued Boolean functions, Unnamed Item, Dense polynomial multiplication with reduced array manipulation overhead, On the tensor rank of multiplication in finite extensions of finite fields and related issues in algebraic geometry, A lower bound on determinantal complexity, Lower bounds in algebraic computational complexity