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

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

Dokumenter

  • Markus Bläser
  • Vladimir Lysikov

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.

OriginalsprogEngelsk
Titel45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020
RedaktørerJavier Esparza, Daniel Kral�, Daniel Kral�
Antal sider15
ForlagSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Publikationsdato2020
Artikelnummer17
ISBN (Elektronisk)9783959771597
DOI
StatusUdgivet - 2020
Begivenhed45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020 - Prague, Tjekkiet
Varighed: 25 aug. 202026 aug. 2020

Konference

Konference45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020
LandTjekkiet
ByPrague
Periode25/08/202026/08/2020
NavnLeibniz International Proceedings in Informatics, LIPIcs
Vol/bind170
ISSN1868-8969

Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk


Ingen data tilgængelig

ID: 249161725