Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
From MaRDI portal
Publication:5020726
DOI10.1137/19M124695XOpenAlexW3217451041WikidataQ114074260 ScholiaQ114074260MaRDI QIDQ5020726
Josh Alman, Virginia Vassilevska Williams
Publication date: 7 January 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1810.08671
Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Multilinear algebra, tensor calculus (15A69)
Related Items
Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science, Flip Graphs for Matrix Multiplication, Bijecting hidden symmetries for skew staircase shapes, An output-sensitive algorithm for all-pairs shortest paths in directed acyclic graphs, New lower bounds for matrix multiplication and, Unnamed Item
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
