Barriers for fast matrix multiplication from irreversibility
From MaRDI portal
Publication:5158496
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
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
