Slice rank of block tensors and irreversibility of structure tensors of algebras

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Standard

Slice rank of block tensors and irreversibility of structure tensors of algebras. / Bläser, Markus; Lysikov, Vladimir.

45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020. red. / Javier Esparza; Daniel Kral�; Daniel Kral�. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. 17 (Leibniz International Proceedings in Informatics, LIPIcs, Bind 170).

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Harvard

Bläser, M & Lysikov, V 2020, Slice rank of block tensors and irreversibility of structure tensors of algebras. i J Esparza, D Kral� & D Kral� (red), 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020., 17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Leibniz International Proceedings in Informatics, LIPIcs, bind 170, 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, Prague, Tjekkiet, 25/08/2020. https://doi.org/10.4230/LIPIcs.MFCS.2020.17

APA

Bläser, M., & Lysikov, V. (2020). Slice rank of block tensors and irreversibility of structure tensors of algebras. I J. Esparza, D. Kral�, & D. Kral� (red.), 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020 [17] Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Leibniz International Proceedings in Informatics, LIPIcs Bind 170 https://doi.org/10.4230/LIPIcs.MFCS.2020.17

Vancouver

Bläser M, Lysikov V. Slice rank of block tensors and irreversibility of structure tensors of algebras. I Esparza J, Kral� D, Kral� D, red., 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2020. 17. (Leibniz International Proceedings in Informatics, LIPIcs, Bind 170). https://doi.org/10.4230/LIPIcs.MFCS.2020.17

Author

Bläser, Markus ; Lysikov, Vladimir. / Slice rank of block tensors and irreversibility of structure tensors of algebras. 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020. red. / Javier Esparza ; Daniel Kral� ; Daniel Kral�. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. (Leibniz International Proceedings in Informatics, LIPIcs, Bind 170).

Bibtex

@inproceedings{5f775dc9ad4a41b5a99bb0cecdbe3068,
title = "Slice rank of block tensors and irreversibility of structure tensors of algebras",
abstract = "Determining the exponent of matrix multiplication ω is one of the central open problems in algebraic complexity theory. All approaches to design fast matrix multiplication algorithms follow the following general pattern: We start with one “efficient” tensor T of fixed size and then we use a way to get a large matrix multiplication out of a large tensor power of T. In the recent years, several so-called barrier results have been established. A barrier result shows a lower bound on the best upper bound for the exponent of matrix multiplication that can be obtained by a certain restriction starting with a certain tensor. We prove the following barrier over C: Starting with a tensor of minimal border rank satisfying a certain genericity condition, except for the diagonal tensor, it is impossible to prove ω = 2 using arbitrary restrictions. This is astonishing since the tensors of minimal border rank look like the most natural candidates for designing fast matrix multiplication algorithms. We prove this by showing that all of these tensors are irreversible, using a structural characterisation of these tensors. To obtain our result, we relate irreversibility to asymptotic slice rank and instability of tensors and prove that the instability of block tensors can often be decided by looking only on the sizes of nonzero blocks.",
keywords = "Barriers, GIT stability, Matrix multiplication, Slice rank, Tensors",
author = "Markus Bl{\"a}ser and Vladimir Lysikov",
year = "2020",
doi = "10.4230/LIPIcs.MFCS.2020.17",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",
editor = "Javier Esparza and Daniel Kral� and Daniel Kral�",
booktitle = "45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020",
note = "45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020 ; Conference date: 25-08-2020 Through 26-08-2020",

}

RIS

TY - GEN

T1 - Slice rank of block tensors and irreversibility of structure tensors of algebras

AU - Bläser, Markus

AU - Lysikov, Vladimir

PY - 2020

Y1 - 2020

N2 - Determining the exponent of matrix multiplication ω is one of the central open problems in algebraic complexity theory. All approaches to design fast matrix multiplication algorithms follow the following general pattern: We start with one “efficient” tensor T of fixed size and then we use a way to get a large matrix multiplication out of a large tensor power of T. In the recent years, several so-called barrier results have been established. A barrier result shows a lower bound on the best upper bound for the exponent of matrix multiplication that can be obtained by a certain restriction starting with a certain tensor. We prove the following barrier over C: Starting with a tensor of minimal border rank satisfying a certain genericity condition, except for the diagonal tensor, it is impossible to prove ω = 2 using arbitrary restrictions. This is astonishing since the tensors of minimal border rank look like the most natural candidates for designing fast matrix multiplication algorithms. We prove this by showing that all of these tensors are irreversible, using a structural characterisation of these tensors. To obtain our result, we relate irreversibility to asymptotic slice rank and instability of tensors and prove that the instability of block tensors can often be decided by looking only on the sizes of nonzero blocks.

AB - Determining the exponent of matrix multiplication ω is one of the central open problems in algebraic complexity theory. All approaches to design fast matrix multiplication algorithms follow the following general pattern: We start with one “efficient” tensor T of fixed size and then we use a way to get a large matrix multiplication out of a large tensor power of T. In the recent years, several so-called barrier results have been established. A barrier result shows a lower bound on the best upper bound for the exponent of matrix multiplication that can be obtained by a certain restriction starting with a certain tensor. We prove the following barrier over C: Starting with a tensor of minimal border rank satisfying a certain genericity condition, except for the diagonal tensor, it is impossible to prove ω = 2 using arbitrary restrictions. This is astonishing since the tensors of minimal border rank look like the most natural candidates for designing fast matrix multiplication algorithms. We prove this by showing that all of these tensors are irreversible, using a structural characterisation of these tensors. To obtain our result, we relate irreversibility to asymptotic slice rank and instability of tensors and prove that the instability of block tensors can often be decided by looking only on the sizes of nonzero blocks.

KW - Barriers

KW - GIT stability

KW - Matrix multiplication

KW - Slice rank

KW - Tensors

UR - http://www.scopus.com/inward/record.url?scp=85090510588&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.MFCS.2020.17

DO - 10.4230/LIPIcs.MFCS.2020.17

M3 - Article in proceedings

AN - SCOPUS:85090510588

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020

A2 - Esparza, Javier

A2 - Kral�, Daniel

A2 - Kral�, Daniel

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020

Y2 - 25 August 2020 through 26 August 2020

ER -

ID: 249161725