Some elementary proofs of lower bounds in complexity theory

DOI10.1016/0024-3795(78)90005-8zbMath0374.15008OpenAlexW2155851636MaRDI 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

Algebraic systems of matrices (15A30) Quadratic and bilinear forms, inner products (15A63)

Related Items (7)

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 ⋮ On commutativity and approximation ⋮ Algebraic and computational properties of a set of (0,1) matrices with prescribed sum

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Some elementary proofs of lower bounds in complexity theory