Rectangular matrix multiplication revisited

DOI10.1006/jcom.1997.0438zbMath0872.68052OpenAlexW2089311600MaRDI QIDQ1361875

Don Coppersmith

Publication date: 28 July 1997

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

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

Mathematics Subject Classification ID

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

Related Items (29)

Quantum and approximation algorithms for maximum witnesses of Boolean matrix products ⋮ Faster algorithms for finding lowest common ancestors in directed acyclic graphs ⋮ Faster combinatorial algorithms for determinant and Pfaffian ⋮ Fast dynamic transitive closure with lookahead ⋮ The shifted number system for fast linear algebra on integer matrices ⋮ Nonuniform ACC Circuit Lower Bounds ⋮ The Closest Pair Problem under the Hamming Metric ⋮ A scalable approach to computing representative lowest common ancestor in directed acyclic graphs ⋮ Induced subgraph isomorphism: are some patterns substantially easier than others? ⋮ A Path Cover Technique for LCAs in Dags ⋮ All-pairs bottleneck paths in vertex weighted graphs ⋮ A fast output-sensitive algorithm for Boolean matrix multiplication ⋮ Fast matrix multiplication and its algebraic neighbourhood ⋮ Computing the sign or the value of the determinant of an integer matrix, a complexity survey. ⋮ A note on the multiplication of sparse matrices ⋮ All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time ⋮ Further Limitations of the Known Approaches for Matrix Multiplication ⋮ Faster Combinatorial Algorithms for Determinant and Pfaffian ⋮ Fast rectangular matrix multiplication and some applications ⋮ BRNGLR: a cubic Tomita-style GLR parsing algorithm ⋮ High-dimensional approximate \(r\)-nets ⋮ Open problems around exact algorithms ⋮ On minimum witnesses for Boolean matrix multiplication ⋮ On the complexity of fixed parameter clique and dominating set ⋮ Faster multi-witnesses for Boolean matrix multiplication ⋮ Fast algorithms for the Sylvester equation \(AX-XB^{T}=C\) ⋮ A note on compressed sensing and the complexity of matrix multiplication ⋮ Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem ⋮ Fast rectangular matrix multiplication and applications

Cites Work

• How to multiply matrices faster
• Matrix multiplication via arithmetic progressions
• Gaussian elimination is not optimal
• Relative bilinear complexity and matrix multiplication.
• Rapid Multiplication of Rectangular Matrices
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression

This page was built for publication: Rectangular matrix multiplication revisited