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.ITCS.2020.10
URN: urn:nbn:de:0030-drops-116956
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11695/
Conner, Austin ;
Landsberg, Joseph M. ;
Gesmundo, Fulvio ;
Ventura, Emanuele
Kronecker Powers of Tensors and Strassen’s Laser Method
Abstract
We answer a question, posed implicitly in [P. Bürgisser et al., 1997] and explicitly in [M. Bläser, 2013], showing the border rank of the Kronecker square of the little Coppersmith-Winograd tensor is the square of the border rank of the tensor for all q>2, a negative result for complexity theory. We further show that when q>4, the analogous result holds for the Kronecker cube. In the positive direction, we enlarge the list of explicit tensors potentially useful for the laser method. We observe that a well-known tensor, the 3 × 3 determinant polynomial regarded as a tensor, det_3 ∈ C^9 ⊗ C^9 ⊗ C^9, could potentially be used in the laser method to prove the exponent of matrix multiplication is two. Because of this, we prove new upper bounds on its Waring rank and rank (both 18), border rank and Waring border rank (both 17), which, in addition to being promising for the laser method, are of interest in their own right. We discuss "skew" cousins of the little Coppersmith-Winograd tensor and indicate why they may be useful for the laser method. We establish general results regarding border ranks of Kronecker powers of tensors, and make a detailed study of Kronecker squares of tensors in C^3 ⊗ C^3 ⊗ C^3.
BibTeX - Entry
@InProceedings{conner_et_al:LIPIcs:2020:11695,
author = {Austin Conner and Joseph M. Landsberg and Fulvio Gesmundo and Emanuele Ventura},
title = {{Kronecker Powers of Tensors and Strassen’s Laser Method}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {10:1--10:28},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-134-4},
ISSN = {1868-8969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11695},
URN = {urn:nbn:de:0030-drops-116956},
doi = {10.4230/LIPIcs.ITCS.2020.10},
annote = {Keywords: Matrix multiplication complexity, Tensor rank, Asymptotic rank, Laser method}
}
|
Keywords: |
|
Matrix multiplication complexity, Tensor rank, Asymptotic rank, Laser method |
|
Collection: |
|
11th Innovations in Theoretical Computer Science Conference (ITCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
06.01.2020 |
