Some elementary proofs of lower bounds in complexity theory

DOI10.1016/0024-3795(78)90005-8MaRDI QIDQ1245277zbMATH OpenOpenAlexFDO

Authors J. 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)

Cites work

• Algebras Having Linear Multiplicative Complexities
• Base tensorielle des matrices de Hankel (ou de Toeplitz). Applications
• Berechnung und Programm. I
• Berechnung und Programm. II
• Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear Forms
• scientific article; zbMATH DE number 3461412 (Why is no real title available?)
• scientific article; zbMATH DE number 3514983 (Why is no real title available?)
• scientific article; zbMATH DE number 3568024 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• scientific article; zbMATH DE number 3408906 (Why is no real title available?)
• scientific article; zbMATH DE number 3198815 (Why is no real title available?)
• scientific article; zbMATH DE number 3090508 (Why is no real title available?)
• On Minimizing the Number of Multiplications Necessary for Matrix Multiplication
• On multiplication of 2 2 matrices
• On the complexity of quaternion multiplication
• On the number of multiplications necessary to compute certain functions
• On the Number of Multiplications Required for Matrix Multiplication
• The complexity of vector-products
• Universality of iterated networks

Cited in

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1245277)