Some elementary proofs of lower bounds in complexity theory

DOI10.1016/0024-3795(78)90005-8zbMath0374.15008MaRDI QIDQ1245277

Jan van Leeuwen, Peter van Emde Boas

Publication date: 1978

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0024-3795(78)90005-8

Mathematics Subject Classification ID

15A30: Algebraic systems of matrices

15A63: Quadratic and bilinear forms, inner products

Related Items

On commutativity and approximation, The complexity of basic complex operations, Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics, The complexity of vector-products, On the optimal computation of a set of symmetric and persymmetric bilinear forms, Lower bounds of the complexity of linear algebras, Algebraic and computational properties of a set of (0,1) matrices with prescribed sum

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Base tensorielle des matrices de Hankel (ou de Toeplitz). Applications
• On the complexity of quaternion multiplication
• The complexity of vector-products
• On multiplication of 2 \(\times\) 2 matrices
• Berechnung und Programm. I
• Berechnung und Programm. II
• Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear Forms
• On the Number of Multiplications Required for Matrix Multiplication
• Algebras Having Linear Multiplicative Complexities
• Universality of iterated networks
• On the number of multiplications necessary to compute certain functions
• On Minimizing the Number of Multiplications Necessary for Matrix Multiplication