An ((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-8MaRDI QIDQ1254853zbMATH OpenOpenAlexFDO

Authors 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

• An Algorithm for the Computation of Linear Forms
• scientific article; zbMATH DE number 3085857 (Why is no real title available?)
• 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

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