Irreversibility of structure tensors of modules

DOI10.1007/S13348-022-00361-WMaRDI QIDQ6157481zbMATH OpenOpenAlexWikidataFDO

Authors Maciej Wojtala

Publication date 11 May 2023

Published in Collectanea Mathematica (Search for Journal in Brave)

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

zbMATH Keywords

matrix multiplication complexityminimal border rank tensorsstructure tensors for modules

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Secant varieties, tensor rank, varieties of sums of powers (14N07)

Abstract: Determining the matrix multiplication exponent $omega$ is one of the greatest open problems in theoretical computer science. We show that it is impossible to prove $omega=2$ by starting with structure tensors of modules of fixed degree and using arbitrary restrictions. It implies that the same is impossible by starting with $1_A$-generic non-diagonal tensors of fixed size with minimal border rank. This generalizes the work of Bl"aser and Lysikov [3]. Our methods come from both commutative algebra and complexity theory.

Recommendations

• Further limitations of the known approaches for matrix multiplication
• Polynomials and the exponent of matrix multiplication
• On cap sets and the group-theoretic approach to matrix multiplication
• Bounds on complexity of matrix multiplication away from Coppersmith-Winograd tensors
• Relative bilinear complexity and matrix multiplication.

Cites work

• scientific article; zbMATH DE number 4092385 (Why is no real title available?)
• scientific article; zbMATH DE number 7559388 (Why is no real title available?)
• scientific article; zbMATH DE number 7564426 (Why is no real title available?)
• Abelian tensors
• Gaussian elimination is not optimal
• Improved bound for complexity of matrix multiplication
• Matrix multiplication via arithmetic progressions
• Powers of tensors and fast matrix multiplication

Cited in

(1)

• A refined laser method and faster matrix multiplication

This page was built for publication: Irreversibility of structure tensors of modules

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