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

DOI10.1016/0304-3975(78)90016-6MaRDI QIDQ1249939zbMATH OpenOpenAlexWikidataFDO

Authors 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)

Cites work

• scientific article; zbMATH DE number 3162280 (Why is no real title available?)
• scientific article; zbMATH DE number 3591381 (Why is no real title available?)
• On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials
• On the number of multiplications necessary to compute certain functions
• Polynomials with Rational Coefficients Which are Hard to Compute
• Semantics of context-free languages: Correction

Cited in

(11)

• A new method to obtain lower bounds for polynomial evaluation
• On the representation of rational functions of bounded complexity
• On Kolmogorov complexity in the real Turing machine setting
• 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
• Simplified lower bounds for polynomials with algebraic coefficients
• On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant
• On the additive complexity of polynomials
• Time-space tradeoffs in algebraic complexity theory

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

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