Beyond Bilinear Complexity: What Works and What Breaks with Many Modes?
TL;DR
This paper explores the algebraic complexity of $d$-mode tensors for $d \geq 4$, a regime where the long-standing equivalence between tensor rank and circuit complexity (true for $d=3$) finally breaks down. By bridging algebraic complexity with algorithmic graph theory via "graph tensors," the authors provide new upper bounds for both rank and circuit complexity while proving that the "nice" property of submultiplicativity for circuit complexity likely fails for tensors with many modes.
What Problem Does This Paper Address?
In the world of algebraic complexity, 3-mode tensors (bilinear maps) are the superstars, primarily because they describe matrix multiplication. For these 3-mode tensors, we have a beautiful symmetry: their asymptotic rank and their asymptotic circuit complexity are essentially the same.
However, many important problems—like detecting hypercliques in graphs or understanding multi-party quantum states—involve tensors with four or more modes. In this "higher-order" regime, the math gets messy. The neat correspondence between rank and circuit complexity disappears, and the tools we used for matrix multiplication don't always scale. This paper aims to map out this intermediate territory, determining which complexity measures still work, which ones break, and how we can bound the cost of computing these high-mode tensors.
Methods
The authors' primary weapon is the Graph Tensor ($T_H$).
- The Bridge: They represent tensors using undirected graphs where vertices correspond to modes and edges represent entanglements (or shared indices). This allows them to translate problems in multilinear algebra into problems in graph theory.
- Treewidth and Line Graphs: To bound circuit complexity, they use the "treewidth" of the line graph of the underlying graph. If a graph has a simple structure (low treewidth), the corresponding tensor has a low-complexity arithmetic circuit.
- The Laser Method: They adapt Strassen’s famous "laser method"—originally designed for 3-mode matrix multiplication—to $d$-mode tensors to derive new upper bounds on asymptotic rank.
- Fine-Grained Reductions: To study whether circuit complexity is "submultiplicative" (i.e., if $C(T \otimes U) \leq C(T)C(U)$), they use reductions from the Hyperclique Conjecture and the hardness of the Permanent.
Datasets
As a theoretical computer science paper, it does not use traditional training datasets. Instead, it evaluates its methods through:
- Graph Decompositions: The authors used computer-aided optimization to find the best fractional decompositions of small graphs (like $K_4$ and $K_5$) into low-rank and low-treewidth components.
- Benchmark Tensors: They analyze specific "folklore" tensors like the Product of Inner Products (PIP) and the $k$-matching tensor to demonstrate the separation between rank and circuit complexity.
Key Insights and Ideas
- The Great Divergence: For $d \geq 4$, rank and circuit complexity are fundamentally different. A tensor can have a very high rank (hard to decompose into simple products) but a very low circuit complexity (easy to compute via a clever algorithm).
- Submultiplicativity is a Trap: In 3 modes, if you have two easy tensors, their Kronecker product is also easy. The authors show that for $d \geq 8$ modes, this likely fails. If circuit complexity were submultiplicative, it would imply a breakthrough in fine-grained complexity (e.g., solving the Hyperclique problem much faster than currently thought possible).
- Fractional Graph Tensors: The authors introduce the concept of "fractional" graphs to represent Kronecker products more flexibly. This allows them to use linear programming to minimize complexity exponents by "covering" a complex graph with simpler, fractional pieces.
Key Results
- Asymptotic Rank: The authors prove that for any $d$-mode tensor ($d \geq 4$), the asymptotic rank exponent is at most $0.772318(d - 1)$. This generalizes and improves upon Strassen’s classic $2\omega/3$ bound.
- Circuit Complexity: They establish a general upper bound for the circuit complexity exponent of generic $d$-mode tensors at $d/2 + 1$.
- Optimized Small Orders: For specific cases, they achieved tighter bounds:
- 4-mode tensors: Circuit complexity exponent $\leq 2.2967$.
- 5-mode tensors: Circuit complexity exponent $\leq 2.8774$.
- Conditional Hardness: They show that assuming the Hyperclique Conjecture, submultiplicativity for circuit complexity fails starting at $d=8$ modes.
Limitations and Future Work
- The Gap: There is still a significant gap between the lower bounds (derived from "flattening" tensors into matrices) and the upper bounds provided in this paper.
- Unconditional Proofs: The failure of submultiplicativity is currently "conditional" on complexity conjectures. Proving this unconditionally would be a major result in circuit lower bounds, which is notoriously difficult.
- Scaling the Search: The computer-aided optimization used for $d=4$ and $d=5$ becomes computationally expensive for larger $d$. Developing more systematic ways to find optimal graph decompositions is a clear next step.
Summary updated