Lower bounds for the non-linear complexity of algebraic computation trees with integer inputs

DOI10.1007/BF01200063zbMath0774.68062OpenAlexW2023899121MaRDI QIDQ685715

Michael D. Hirsch

Publication date: 10 October 1993

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

Full work available at URL: https://doi.org/10.1007/bf01200063

zbMATH Keywords

lower boundsreal algebraic geometrynonlinear complexitycomputation tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Real polynomials: location of zeros (26C10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Real rational functions (26C15)

Related Items (2)

Semi-algebraic decision complexity, the real spectrum, and degree ⋮ Algebraic decision trees and Euler characteristics

Cites Work

• How to multiply matrices faster
• Matrix multiplication via arithmetic progressions
• A lower bound for the integer element distinctness problem
• Lower bounds for algebraic decision trees
• Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
• On the Betti Numbers of Real Varieties

This page was built for publication: Lower bounds for the non-linear complexity of algebraic computation trees with integer inputs