The complexity of bilinear maps (equivalently, of $3$-mode tensors) has been studied extensively, most notably in the context of matrix multiplication. While circuit complexity and tensor rank coincide asymptotically for $3$-mode tensors, this correspondence breaks down for $d \geq 4$ modes. As a result, the complexity of $d$-mode tensors for larger fixed $d$ remains poorly understood, despite its relevance, e.g., in fine-grained complexity. Our paper explores this intermediate regime.
First, we give a ``graph-theoretic'' proof of Strassen's $2\omega/3$ bound on the asymptotic rank exponent of $3$-mode tensors. Our proof directly generalizes to an upper bound of $(d-1)\omega/3$ for $d$-mode tensors. Using refined techniques available only for $d\geq 4$ modes, we improve this bound beyond the current state of the art for $\omega$. We also obtain a bound of $d/2+1$ on the asymptotic exponent of \emph{circuit complexity} of generic $d$-mode tensors and optimized bounds for $d \in \{4,5\}$.
To the best of our knowledge, asymptotic circuit complexity (rather than rank) of tensors has not been studied before.To obtain a robust theory, we first ask whether low complexity of $T$ and $U$ imply low complexity of their Kronecker product $T \otimes U$. While this crucially holds for rank (and thus for circuit complexity in $3$ modes), we show that assumptions from fine-grained complexity rule out such a \emph{submultiplicativity} for the circuit complexity of tensors with many modes. In particular, assuming the Hyperclique Conjecture, this failure occurs already for $d=8$ modes. Nevertheless, we can salvage a restricted notion of submultiplicativity.
From a technical perspective, our proofs heavily make use of the \emph{graph tensors} $T_H$, as employed by Christandl and Zuiddam ({\em Comput.~Complexity}~28~(2019)~27--56) and Christandl, Vrana and Zuiddam ({\em Comput.~Complexity}~28~(2019)~57--111), whose modes correspond to the vertices of undirected graphs $H$. We make the simple but conceptually crucial observation that Kronecker products $T_G \otimes T_H$ are isomorphic to $T_{G+H}$, and that $G$ and $H$ may also be \emph{fractional} graphs. By asymptotically converting generic tensors to specific graph tensors, we can use nontrivial results from algorithmic graph theory to study the rank and complexity of $d$-mode tensors for fixed $d$.