Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
From MaRDI portal
Publication:6139832
DOI10.1137/19m124695xzbMath1528.68419OpenAlexW3217451041WikidataQ114074260 ScholiaQ114074260MaRDI QIDQ6139832
Virginia Vassilevska Williams, Josh Alman
Publication date: 19 December 2023
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/19m124695x
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Multilinear algebra, tensor calculus (15A69)
Cites Work
- On sunflowers and matrix multiplication
- Progression-free sets in \(\mathbb{Z}_4^n\) are exponentially small
- On large subsets of \(\mathbb{F}_q^n\) with no three-term arithmetic progression
- Matrix multiplication via arithmetic progressions
- Bounds for matchings in nonabelian groups
- Gaussian elimination is not optimal
- Improved bound for complexity of matrix multiplication
- Fast Matrix Multiplication
- Powers of tensors and fast matrix multiplication
- Relative bilinear complexity and matrix multiplication.
- Partial and Total Matrix Multiplication
- On the Asymptotic Complexity of Matrix Multiplication
- On cap sets and the group-theoretic approach to matrix multiplication
- The growth rate of tri-colored sum-free sets
- Further Limitations of the Known Approaches for Matrix Multiplication
- Geometry and Complexity Theory
- Multiplying matrices faster than coppersmith-winograd
