Fast Matrix Multiplication

DOI10.1145/2746539.2746554zbMath1321.65063arXiv1411.5414OpenAlexW4290960540MaRDI QIDQ2941553

Yuval Filmus, François Le Gall, Andris Ambainis

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

lower boundsalgebraic complexity theorymatrix multiplication

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (22)

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 ⋮ Skew-polynomial-sparse matrix multiplication ⋮ Tensor surgery and tensor rank ⋮ Concise tensors of minimal border rank ⋮ 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 ⋮ Further Limitations of the Known Approaches for Matrix Multiplication ⋮ A Rank 18 Waring Decomposition of sM_〈3〉 with 432 Symmetries ⋮ Unnamed Item ⋮ 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 ⋮ Upgrading Subgroup Triple-Product-Property Triples ⋮ Barriers for fast matrix multiplication from irreversibility ⋮ Unnamed Item ⋮ Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication ⋮ Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication

Uses Software

• Graphs

Cites Work

• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Unnamed Item

This page was built for publication: Fast Matrix Multiplication