Irreversibility of Structure Tensors of Modules
Maciej Wojtala · arXiv (Cornell University) · 2021
Determining the matrix multiplication exponent $ω$ is one of the greatest open problems in theoretical computer science. We show that it is impossible to prove $ω= 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äser and Lysikov [3]. Our methods come from both commutative algebra and complexity theory.