Strassen's theory of bilinear complexity provides a mathematical characterization of the arithmetic complexity of primitives such as matrix multiplication via the rank of tensors. However, this connection to tensor rank is known to be unreliable in higher degrees of multilinearity. In this work, we highlight an unexplored connection between a generalized notion of tensor rank, defined in Naslund's framework of partition ranks, and multiplicative complexity.
These partition ranks allow us to control the multiplicative complexity, and thus arithmetic complexity, in any constant degree of multilinearity from below, while recovering Strassen's seminal characterization in the bilinear case. This enables novel potential applications of rank-based approaches to fine-grained algorithms and complexity problems, such as the hyperclique conjecture of Lincoln-Williams-Vassilevska Williams (SODA 2018).
Moreover, we exhibit connections to established notions of rank, such as tensor slice rank (in the sense of Tao and Sawin), as well as its symmetric variant. For computing the latter symmetric variant, we point out a simple NP-hardness proof, contrasting with the more involved NP-hardness proof for ordinary, non-symmetric tensor slice rank by Bläser et al. (SODA 2021).
Blogger's Review: This paper reveals a profound connection between partition rank and multiplicative complexity, providing a fresh perspective for complexity theory. By controlling the arithmetic complexity across multilinearity, the authors open up new avenues for future algorithmic research. The NP-hardness proof of the symmetric variant also lays a significant theoretical foundation for related fields.