Irreversibility of structure tensors of modules

DOI10.1007/S13348-022-00361-WzbMATH Open1523.68037arXiv2110.01684OpenAlexW3203660917WikidataQ114219987 ScholiaQ114219987MaRDI QIDQ6157481FDOQ6157481

Authors: Maciej Wojtala 

Publication date: 11 May 2023

Published in: Collectanea Mathematica (Search for Journal in Brave)

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.

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

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.

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)

Cites Work

• Powers of tensors and fast matrix multiplication
• Gaussian elimination is not optimal
• Improved bound for complexity of matrix multiplication
• Matrix multiplication via arithmetic progressions
• Title not available (Why is that?)
• Abelian tensors
• Title not available (Why is that?)
• Title not available (Why is that?)

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)