Strassen 的双线性复杂性理论为诸如矩阵乘法等基本运算的算术复杂性提供了数学表征，主要通过张量的秩来实现。然而，在更高的多线性度中，这一与张量秩的联系被认为是不可靠的。在本研究中，我们强调了一种尚未探讨的关系，即在 Naslund 的分区秩框架下定义的广义张量秩与乘法复杂性之间的联系。
这些分区秩使我们能够从下方控制乘法复杂性，因此也控制算术复杂性，适用于任意常数多线性度，同时恢复 Strassen 在双线性情况下的开创性表征。这一发现为基于秩的方法在细粒度算法和复杂性问题中的新应用提供了可能性，例如 Lincoln-Williams-Vassilevska Williams 的超完全图猜想（SODA 2018）。
此外，我们还展示了与已有的秩概念的联系，例如张量切片秩（根据 Tao 和 Sawin 的定义）及其对称变体。对于计算后者的对称变体，我们指出了一个简单的 NP-困难性证明，这与 Bläser 等人（SODA 2021）对普通非对称张量切片秩的复杂证明形成对比。
博主点评： 本文揭示了分区秩与乘法复杂性之间的深刻联系，为复杂性理论提供了新的视角。通过控制多线性度的算术复杂性，作者为未来的算法研究开辟了新的可能性，值得关注。其对称变体的 NP-困难性证明也为相关领域提供了重要的理论基础。