Barriers for fast matrix multiplication from irreversibility

DOI10.4086/toc.2021.v017a002OpenAlexW3199350616MaRDI QIDQ5158496

Péter Vrana, Matthias Christandl, Jeroen Zuiddam

Publication date: 25 October 2021

Published in: Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

algebraic complexitytensor ranktensorsbarriersmatrix multiplication

Mathematics Subject Classification ID

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

Related Items

Bounds on complexity of matrix multiplication away from Coppersmith-Winograd tensors ⋮ Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science ⋮ Rank and border rank of Kronecker powers of tensors and Strassen's laser method

Cites Work

• Unnamed Item
• Unnamed Item
• On large subsets of \(\mathbb{F}_q^n\) with no three-term arithmetic progression
• Matrix multiplication via arithmetic progressions
• Abelian tensors
• Asymptotic tensor rank of graph tensors: beyond matrix multiplication
• Gaussian elimination is not optimal
• Fast Matrix Multiplication
• Quantum entanglement
• Powers of tensors and fast matrix multiplication
• Relative bilinear complexity and matrix multiplication.
• The asymptotic spectrum of tensors.
• On cap sets and the group-theoretic approach to matrix multiplication
• Degeneration and complexity of bilinear maps: Some asymptotic spectra.
• Asymptotic entanglement transformation between W and GHZ states
• Universal points in the asymptotic spectrum of tensors
• Multiplying matrices faster than coppersmith-winograd
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression