Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials
From MaRDI portal
Publication:1249939
DOI10.1016/0304-3975(78)90016-6zbMATH Open0387.68034OpenAlexW1965589490WikidataQ114214853 ScholiaQ114214853MaRDI QIDQ1249939FDOQ1249939
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
Cites Work
- Title not available (Why is that?)
- Polynomials with Rational Coefficients Which are Hard to Compute
- Semantics of context-free languages: Correction
- On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials
- On the number of multiplications necessary to compute certain functions
- Title not available (Why is that?)
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)
