Complexity lower bounds for approximation algebraic computation trees

DOI10.1006/jcom.1999.0519zbMath0959.68143OpenAlexW1970197763WikidataQ57733282 ScholiaQ57733282MaRDI QIDQ1578509

Felipe Cucker, Dima Yu. Grigoriev

Publication date: 3 September 2000

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/feec4df32c400a7bc54de569d242274f478cd275

zbMATH Keywords

approximate computations

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (1)

DECISION TREES DO NOT GENERALIZE TO NEW VARIATIONS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the topology of algorithms. I
• On the worst-case arithmetic complexity of approximating zeros of polynomials
• An exponential lower bound on the size of algebraic decision trees for MAX
• Nearly sharp complexity bounds for multiprocessor algebraic computations
• Lower bounds for arithmetic networks
• Complexity estimates depending on condition and round-off error
• The Computational Complexity of Continued Fractions

This page was built for publication: Complexity lower bounds for approximation algebraic computation trees