Further Limitations of the Known Approaches for Matrix Multiplication

DOI10.4230/LIPIcs.ITCS.2018.25zbMath1462.68076arXiv1712.07246OpenAlexW2964026456MaRDI QIDQ4993288

Josh Alman, Virginia Vassilevska Williams

Publication date: 15 June 2021

Full work available at URL: https://arxiv.org/abs/1712.07246

zbMATH Keywords

lower boundmatrix multiplicationmonomial degenerationstructural tensor of addition mod \(p\)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Basic linear algebra (15A99)

Related Items (13)

The Faddeev-LeVerrier algorithm and the Pfaffian ⋮ Bounds on complexity of matrix multiplication away from Coppersmith-Winograd tensors ⋮ New applications of the polynomial method: The cap set conjecture and beyond ⋮ Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science ⋮ Bad and good news for Strassen's laser method: border rank of \(\mathrm{Perm}_3\) and strict submultiplicativity ⋮ New lower bounds for matrix multiplication and ⋮ Weighted slice rank and a minimax correspondence to Strassen's spectra ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Limits on the Universal method for matrix multiplication ⋮ Rank and border rank of Kronecker powers of tensors and Strassen's laser method ⋮ Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication ⋮ Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication

Cites Work

• On large subsets of \(\mathbb{F}_q^n\) with no three-term arithmetic progression
• Matrix multiplication via arithmetic progressions
• \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication
• Rectangular matrix multiplication revisited
• 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.
• New Fast Algorithms for Matrix Operations
• Partial and Total Matrix Multiplication
• On the Asymptotic Complexity of Matrix Multiplication
• On cap sets and the group-theoretic approach to matrix multiplication
• Multiplying matrices faster than coppersmith-winograd
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression

This page was built for publication: Further Limitations of the Known Approaches for Matrix Multiplication