On the additive complexity of polynomials

DOI10.1016/0304-3975(80)90068-7zbMath0469.68044OpenAlexW2081103509WikidataQ126352409 ScholiaQ126352409MaRDI QIDQ1157163

Claus Peter Schnorr, J. P. Van de Wiele

Publication date: 1980

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(80)90068-7

zbMATH Keywords

arithmetic complexityevaluation of polynomials

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Computability of the additive complexity of algebraic circuits with root extracting, Lower bounds for polynomials with algebraic coefficients, Lower bounds for the complexity of polynomials, On the representation of rational functions of bounded complexity, Lower bounds in algebraic computational complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Lower bounds for polynomials with algebraic coefficients
• Evaluation of polynomials with super-preconditioning
• Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials
• An Algorithm for the Computation of Linear Forms
• On the Number of Additions to Compute Specific Polynomials
• Polynomials with Rational Coefficients Which are Hard to Compute
• On the number of multiplications necessary to compute certain functions
• On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials