License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2022.9
URN: urn:nbn:de:0030-drops-165716
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16571/
Derksen, Harm ;
Makam, Visu ;
Zuiddam, Jeroen
Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors
Abstract
Since the seminal works of Strassen and Valiant it has been a central theme in algebraic complexity theory to understand the relative complexity of algebraic problems, that is, to understand which algebraic problems (be it bilinear maps like matrix multiplication in Strassen’s work, or the determinant and permanent polynomials in Valiant’s) can be reduced to each other (under the appropriate notion of reduction).
In this paper we work in the setting of bilinear maps and with the usual notion of reduction that allows applying linear maps to the inputs and output of a bilinear map in order to compute another bilinear map. As our main result we determine precisely how many independent scalar multiplications can be reduced to a given bilinear map (this number is called the subrank, and extends the concept of matrix diagonalization to tensors), for essentially all (i.e. generic) bilinear maps. Namely, we prove for a generic bilinear map T : V × V → V where dim(V) = n that θ(√n) independent scalar multiplications can be reduced to T. Our result significantly improves on the previous upper bound from the work of Strassen (1991) and Bürgisser (1990) which was n^{2/3 + o(1)}. Our result is very precise and tight up to an additive constant. Our full result is much more general and applies not only to bilinear maps and 3-tensors but also to k-tensors, for which we find that the generic subrank is θ(n^{1/(k-1)}). Moreover, as an application we prove that the subrank is not additive under the direct sum.
The subrank plays a central role in several areas of complexity theory (matrix multiplication algorithms, barrier results) and combinatorics (e.g., the cap set problem and sunflower problem). As a consequence of our result we obtain several large separations between the subrank and tensor methods that have received much interest recently, notably the slice rank (Tao, 2016), analytic rank (Gowers-Wolf, 2011; Lovett, 2018; Bhrushundi-Harsha-Hatami-Kopparty-Kumar, 2020), geometric rank (Kopparty-Moshkovitz-Zuiddam, 2020), and G-stable rank (Derksen, 2020).
Our proofs of the lower bounds rely on a new technical result about an optimal decomposition of tensor space into structured subspaces, which we think may be of independent interest.
BibTeX - Entry
@InProceedings{derksen_et_al:LIPIcs.CCC.2022.9,
author = {Derksen, Harm and Makam, Visu and Zuiddam, Jeroen},
title = {{Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors}},
booktitle = {37th Computational Complexity Conference (CCC 2022)},
pages = {9:1--9:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-241-9},
ISSN = {1868-8969},
year = {2022},
volume = {234},
editor = {Lovett, Shachar},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16571},
URN = {urn:nbn:de:0030-drops-165716},
doi = {10.4230/LIPIcs.CCC.2022.9},
annote = {Keywords: tensors, bilinear maps, complexity, subrank, diagonalization, generic tensors, random tensors, reduction, slice rank}
}
|
Keywords: |
|
tensors, bilinear maps, complexity, subrank, diagonalization, generic tensors, random tensors, reduction, slice rank |
|
Collection: |
|
37th Computational Complexity Conference (CCC 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
11.07.2022 |
