Lower bound for the approximative complexity

DOI10.1016/0304-3975(86)90038-1zbMath0618.68034OpenAlexW1965518937MaRDI QIDQ1822498

Bernhard Griesser

Publication date: 1986

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(86)90038-1

zbMATH Keywords

lower boundscomplexity of polynomials

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Polynomials in general fields (irreducibility, etc.) (12E05)

Related Items (2)

Quiz games as a model for information hiding ⋮ Unifying known lower bounds via geometric complexity theory

Cites Work

• Unnamed Item
• A note on the complexity of approximative evaluation of polynomials
• Definability and fast quantifier elimination in algebraically closed fields
• On commutativity and approximation
• The complexity of partial derivatives
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• The Computational Complexity of Continued Fractions
• Simple Proofs of Lower Bounds for Polynomial Evaluation
• On the number of multiplications necessary to compute certain functions

This page was built for publication: Lower bound for the approximative complexity