2026-07-23T20:14:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27053 2026-07-23T11:36:18Z ddc:004 open_access

Beyond Bilinear Complexity: What Works and What Breaks with Many Modes? Brand, Cornelius Curticapean, Radu Kaski, Petteri Li, Baitian Orzel, Ian Seppelt, Tim Wang, Jiaheng arithmetic circuits tensor rank bilinear complexity graph tensors 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 T_H, as employed by Christandl and Zuiddam (Comput. Complexity 28 (2019) 27-56) and Christandl, Vrana and Zuiddam (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 ⊗ T_H are isomorphic to T_{G+H}, and that G and H may also be 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Cornelius Brand and Radu Curticapean and Petteri Kaski and Baitian Li and Ian Orzel and Tim Seppelt and Jiaheng Wang 2026 Is Part Of LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2026.11 urn:nbn:de:0030-drops-270530 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.11 eng https://creativecommons.org/licenses/by/4.0/legalcode