On degeneration of tensors and Algebras

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

  • Markus Bläser
  • Vladimir Lysikov

An important building block in all current asymptotically fast algorithms for matrix multiplication are tensors with low border rank, that is, tensors whose border rank is equal or very close to their size. To find new asymptotically fast algorithms for matrix multiplication, it seems to be important to understand those tensors whose border rank is as small as possible, so called tensors of minimal border rank. We investigate the connection between degenerations of associative algebras and degenerations of their structure tensors in the sense of Strassen. It allows us to describe an open subset of n × n × n tensors of minimal border rank in terms of smoothability of commutative algebras. We describe the smoothable algebra associated to the Coppersmith-Winograd tensor and prove a lower bound for the border rank of the tensor used in the "easy construction" of Coppersmith and Winograd.

OriginalsprogEngelsk
Titel41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016
RedaktørerAnca Muscholl, Piotr Faliszewski, Rolf Niedermeier
UdgivelsesstedSaarbrücken/Wadern
ForlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publikationsdato1 aug. 2016
Artikelnummer19
ISBN (Elektronisk)9783959770163
DOI
StatusUdgivet - 1 aug. 2016
Eksternt udgivetJa
Begivenhed41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016 - Krakow, Polen
Varighed: 22 aug. 201626 aug. 2016

Konference

Konference41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016
LandPolen
ByKrakow
Periode22/08/201626/08/2016
NavnLeibniz International Proceedings in Informatics, LIPIcs
Vol/bind58
ISSN1868-8969

ID: 232711677