Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials

DOI10.1016/0304-3975(78)90016-6zbMath0387.68034OpenAlexW1965589490WikidataQ114214853 ScholiaQ114214853MaRDI QIDQ1249939

Claus Peter Schnorr

Publication date: 1978

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

Full work available at URL: https://doi.org/10.1016/0304-3975(78)90016-6

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (11)

On Kolmogorov complexity in the real Turing machine setting ⋮ Simplified lower bounds for polynomials with algebraic coefficients ⋮ A note on the complexity of approximative evaluation of polynomials ⋮ Fast computation of the \(N\)-th term of a \(q\)-holonomic sequence and applications ⋮ Some polynomials that are hard to compute ⋮ Lower bounds for polynomials with algebraic coefficients ⋮ On the additive complexity of polynomials ⋮ Time-space tradeoffs in algebraic complexity theory ⋮ A new method to obtain lower bounds for polynomial evaluation ⋮ On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant ⋮ On the representation of rational functions of bounded complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Polynomials with Rational Coefficients Which are Hard to Compute
• On the number of multiplications necessary to compute certain functions
• Semantics of context-free languages: Correction
• On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials

This page was built for publication: Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials