Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication

DOI10.1137/19M124695XMaRDI QIDQ6139832zbMATH OpenOpenAlexWikidataFDO

Authors Josh Alman, Virginia Vassilevska Williams

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

zbMATH Keywords

tensormatrix multiplicationmonomial degeneration

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) 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)

Cites work

• Bounds for matchings in nonabelian groups
• Fast matrix multiplication: limitations of the Coppersmith-Winograd method (extended abstract)
• Further limitations of the known approaches for matrix multiplication
• Gaussian elimination is not optimal
• Geometry and complexity theory
• Improved bound for complexity of matrix multiplication
• Matrix multiplication via arithmetic progressions
• Multiplying matrices faster than coppersmith-winograd
• On cap sets and the group-theoretic approach to matrix multiplication
• On large subsets of \(\mathbb{F}_q^n\) with no three-term arithmetic progression
• On sunflowers and matrix multiplication
• On the Asymptotic Complexity of Matrix Multiplication
• Partial and Total Matrix Multiplication
• Powers of tensors and fast matrix multiplication
• Progression-free sets in \(\mathbb{Z}_4^n\) are exponentially small
• Relative bilinear complexity and matrix multiplication.
• The growth of tri-colored sum-free sets

This page was built for publication: Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6139832)