2026/02/12 by Cornelius Brand, Radu Curticapean, Petteri Kaski +4 · 1 voice · 1 citation
Computer Science · Mathematics · #Bilinear interpolation #Circuit complexity #Complexity and Algorithms in Graphs #Computational complexity theory #Context (archaeology) #Exponent #Mathematical proof #Matrix (chemical analysis) #Rank (graph theory) #Stochastic Gradient Optimization Techniques #Tensor decomposition and applications #Upper and lower bounds #cs.CC
paper · pdf · doi:10.48550/arxiv.2602.11975
openalex publication_date 2026/02/12 · arxiv published 2026/02/12 · arxiv updated 2026/02/12 · openalex created_date 2026/02/14 · openalex updated_date 2026/07/29
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 ≥ 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ω/3 bound on the asymptotic rank exponent of 3-mode tensors. Our proof directly generalizes to an upper bound of (d-1)ω/3 for d-mode tensors. Using refined techniques available only for d≥ 4 modes, we improve this bound beyond the current state of the art for ω. We also obtain a bound of d/2+1 on the asymptotic exponent of circuit complexity of generic d-mode tensors and optimized bounds for d ∈ \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 ⊗ 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 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 graph tensors TH, as employed by Christandl and Zuiddam (\em Comput.~Complexity~28~(2019)~27--56) and [...]