License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.19
URN: urn:nbn:de:0030-drops-64343
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6434/
Go to the corresponding LIPIcs Volume Portal

Bläser, Markus ; Lysikov, Vladimir

On Degeneration of Tensors and Algebras

pdf-format:
LIPIcs-MFCS-2016-19.pdf (0.4 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{blser_et_al:LIPIcs:2016:6434,
  author =	{Markus Bl{\"a}ser and Vladimir Lysikov},
  title =	{{On Degeneration of Tensors and Algebras}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{19:1--19:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6434},
  URN =		{urn:nbn:de:0030-drops-64343},
  doi =		{10.4230/LIPIcs.MFCS.2016.19},
  annote =	{Keywords: bilinear complexity, border rank, commutative algebras, lower bounds}
}

Keywords: bilinear complexity, border rank, commutative algebras, lower bounds
Collection: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Issue Date: 2016
Date of publication: 19.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI