Simple Proofs of Lower Bounds for Polynomial Evaluation

DOI10.1007/978-1-4684-2001-2_3zbMath1467.68070OpenAlexW345028505MaRDI QIDQ4999419

A. Ian Stocks, Edward M. Reingold

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 boundpolynomial evaluationnumber of arithmetic operations

Mathematics Subject Classification ID

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

Related Items (3)

Test complexity of generic polynomials ⋮ A survey of techniques in applied computational complexity ⋮ Lower bound for the approximative complexity

This page was built for publication: Simple Proofs of Lower Bounds for Polynomial Evaluation