论文标题
子班级和标量乘法的最佳减少为通用张量
Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors
论文作者
论文摘要
由于Strassen和Valiant的开创性作品，因此在代数复杂性理论中是一个核心主题，可以理解代数问题的相对复杂性，也就是说，要了解哪些代数问题（无论是在Strassen的工作中矩阵乘法等双线性图），还是在众多的元素中均可归因于其他规定的综合）。 在本文中，我们精确地确定可以将多少个独立的标量乘法还原为给定的双线图（该数字称为子班级，并将矩阵对角线化的概念扩展到张量），从本质上讲，所有（即通用的）双线性图。也就是说，我们证明了通用双线图$ t：v \ times v \ to v $其中$ \ dim（v）= n $ th $θ（\ sqrt {n}）$可以减少到$ t $。我们的结果显着改善了Strassen（1991）和Bürgisser（1990）的工作上的上限，这是$ n^{2/3 + o（1）} $。我们的完整结果更加笼统，不仅适用于双线图和3汤匙，还适用于$ k $ - tensors，我们发现通用子班级为$θ（n^{1/（k-1）}）$。此外，作为一个应用程序，我们证明了子班级在直接总和下不是加性。 子班级在复杂性理论（矩阵乘法算法，障碍结果）和组合（例如，CAP集问题和向日葵问题）中起着核心作用。 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年）和G稳定等级（Derksen，2020）。
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 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 \times V \to V$ where $\dim(V) = n$ that $θ(\sqrt{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 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).
