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-6zbMath0387.68034OpenAlexW1965589490WikidataQ114214853 ScholiaQ114214853MaRDI QIDQ1249939
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
Related Items
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
