Some computational problems in linear algebra as hard as matrix multiplication

DOI10.1007/BF01272518zbMath0774.68056OpenAlexW1983863143MaRDI QIDQ685718

Peter Bürgisser, Thomas Lickteig, Marek Karpinski

Publication date: 10 October 1993

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

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

zbMATH Keywords

derivationsstraight line programscomputation treesOstrowski complexity measure

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Related Items (1)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matrix multiplication via arithmetic progressions
• Fast algorithms for the characteristic polynomial
• The trace invariant and matrix inversion
• On the algorithmic complexity of associative algebras
• The complexity of partial derivatives
• Gaussian elimination is not optimal
• Unitäre Transformationen großer Matrizen
• Berechnung und Programm. I
• Berechnung und Programm. II
• The Computational Complexity of Continued Fractions
• Relative bilinear complexity and matrix multiplication.
• Triangular Factorization and Inversion by Fast Matrix Multiplication
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines

This page was built for publication: Some computational problems in linear algebra as hard as matrix multiplication