An \(\Omega((n/lg\,n)^{1/2})\) lower bound on the number of additions necessary to compute 0-1 polynomials over the ring of integer polynomials

DOI10.1016/0020-0190(79)90018-8zbMath0399.68061OpenAlexW2046588457MaRDI QIDQ1254853

Ronald L. Rivest, J. P. Van de Wiele

Publication date: 1979

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(79)90018-8

zbMATH Keywords

Lower BoundNumber Of AdditionsPolynomials over the Ring of Integer Polynomials

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Unnamed Item
• An Algorithm for the Computation of Linear Forms
• On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials

This page was built for publication: An \(\Omega((n/lg\,n)^{1/2})\) lower bound on the number of additions necessary to compute 0-1 polynomials over the ring of integer polynomials