{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreienidikzh2fj5jgihaqqmcadte2vdzfre6go7pw4j3d4s6z2y2wkq",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mfboykzdcgl2"
  },
  "path": "/report/2026/025",
  "publishedAt": "2026-02-20T06:21:36.000Z",
  "site": "https://eccc.weizmann.ac.il",
  "textContent": "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$.",
  "title": "TR26-025 |  Beyond Bilinear Complexity: What Works and What Breaks with Many Modes? | \n\n\tCornelius Brand, \n\n\tRadu Curticapean, \n\n\tPetteri Kaski, \n\n\tBaitian Li, \n\n\tIan Orzel, \n\n\tTim Seppelt, \n\n\tJiaheng Wang"
}