Barriers for fast matrix multiplication from irreversibility

DOI10.4086/TOC.2021.V017A002MaRDI QIDQ5158496zbMATH OpenOpenAlexFDO

Authors Matthias Christandl, Péter Vrana, Jeroen Zuiddam

Publication date 25 October 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

tensorsbarriersmatrix multiplicationtensor rankalgebraic complexity

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)

Recommendations

• Barriers for fast matrix multiplication from irreversibility
• Slice rank of block tensors and irreversibility of structure tensors of algebras
• Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
• Further limitations of the known approaches for matrix multiplication

Cites work

• scientific article; zbMATH DE number 727424 (Why is no real title available?)
• Abelian tensors
• Asymptotic entanglement transformation between W and GHZ states
• Asymptotic tensor rank of graph tensors: beyond matrix multiplication
• Degeneration and complexity of bilinear maps: Some asymptotic spectra.
• Fast matrix multiplication: limitations of the Coppersmith-Winograd method (extended abstract)
• Gaussian elimination is not optimal
• Limits on the universal method for matrix multiplication
• Matrix multiplication via arithmetic progressions
• 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
• 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
• Powers of tensors and fast matrix multiplication
• Quantum entanglement
• Relative bilinear complexity and matrix multiplication.
• The asymptotic spectrum of tensors.
• Universal points in the asymptotic spectrum of tensors

Cited in

(4)

• Rank and border rank of Kronecker powers of tensors and Strassen's laser method
• A refined laser method and faster matrix multiplication
• 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

This page was built for publication: Barriers for fast matrix multiplication from irreversibility

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