Semi-algebraic complexity -- Additive complexity of matrix computational tasks

DOI10.1006/jcom.1997.0430zbMath0887.68038OpenAlexW2071763554MaRDI QIDQ1361878

Klaus Meer, Thomas Lickteig

Publication date: 26 August 1997

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

Full work available at URL: https://doi.org/10.1006/jcom.1997.0430

zbMATH Keywords

matrix computational tasks

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Some computational problems in linear algebra as hard as matrix multiplication
• How to multiply matrices faster
• Matrix multiplication via arithmetic progressions
• Lectures on the complexity of bilinear problems
• The complexity of partial derivatives
• Semi-algebraic decision complexity, the real spectrum, and degree
• Semi-algebraic complexity of quotients and sign determination of remainders
• On the real spectrum of a ring and its application to semialgebraic geometry
• La topologie du spectre réel
• On the Asymptotic Complexity of Matrix Multiplication
• Taylor expansion of the accumulated rounding error
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On the number of multiplications necessary to compute certain functions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item