Simple proofs of lower bounds for polynomial evaluation

DOI10.1007/978-1-4684-2001-2_3MaRDI QIDQ4999419zbMATH OpenOpenAlexFDO

Authors Edward M. Reingold, A. Ian Stocks

Publication date 6 July 2021

Published in Complexity of Computer Computations (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-1-4684-2001-2_3

zbMATH Keywords

lower boundnumber of arithmetic operationspolynomial evaluation

Mathematics Subject Classification ID

Numerical computation of roots of polynomial equations (65H04) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Fast evaluation of polynomials by rational preparation
• Lower bounds for polynomial evaluation and interpolation problems
• A new method to obtain lower bounds for polynomial evaluation
• Approximate Complex Polynomial Evaluation in Near Constant Work Per Point
• scientific article; zbMATH DE number 1222560

Cited in

(6)

• Test complexity of generic polynomials
• A survey of techniques in applied computational complexity
• Lower bounds for polynomial evaluation and interpolation problems
• Lower bound for the approximative complexity
• scientific article; zbMATH DE number 6796098 (Why is no real title available?)
• Fast evaluation of polynomials by rational preparation

This page was built for publication: Simple proofs of lower bounds for polynomial evaluation

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