Motivated by fast matrix multiplication and recent connections between asymptotic tensor rank and fine-grained complexity, we revisit classical tools from the matrix multiplication literature and develop a framework for obtaining improved asymptotic rank upper bounds for tensors beyond matrix multiplication. In the 1980s, Coppersmith-Winograd and Strassen discovered a series of speedup theorems for asymptotic rank: in certain regimes, one can extract additional terms from a border rank upper bound on a tensor T, and then use these terms to obtain an improved asymptotic rank of T. We establish general speedup theorems that subsume these results and enable quantitative improvements. Two representative applications are: 1) The asymptotic rank of the small Coppersmith-Winograd tensor cw_q is less than its border rank. For instance, we prove ̰{R}(cw₂) < 3.931, improving on ̲{R}(cw₂) = 4. It is known that ̰{R}(cw₂) = 3 would imply ω = 2. 2) A general improvement over Strassen’s bound: we obtain an upper bound below d^{2ω/3} on the asymptotic rank of any d× d× d tensor. To make full use of speedups, we analyze degenerations in which both sides are nontrivial direct sums, a setting where the optimal quantitative bound one can achieve was previously unclear. We do so via an approach we call Strassen calculus: a systematic method for converting such degeneration data into explicit asymptotic rank bounds using Strassen’s theory of the asymptotic spectrum.

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.

We show that the hafnian of a symmetric $2n\times 2n$ matrix of $\operatorname{poly}(n)$-bit integers (which counts the number of perfect matchings of a $2n$-vertex graph) and the number of Hamiltonian cycles of an $n$-vertex directed graph can be computed in time $2^{n-Ω(\sqrt{n})}$, improving and generalizing an earlier algorithm of Björklund, Kaski, and Williams (Algorithmica 2019) that runs in time $2^{n - Ω\left(\sqrt{n/\log \log n}\right)}$. A key tool of our approach is the design of a data structure that supports fast evaluation of high-order derivatives of hafnian and Hamiltonian cycles, which integrates with the new approach on multivariate multipoint evaluation by Bhargava, Ghosh, Guo, Kumar, and Umans (FOCS 2022, JACM 2024).

We study circuits for computing linear transforms defined by Kronecker power matrices. The best-known (unbounded-depth) circuits, including the widely-applied fast Walsh-Hadamard transform and Yates’ algorithm, can be derived from the best-known depth- 2 circuits using known constructions, so we focus particularly on the depth- 2 case. Recent work [Jukna and Sergeev’13; Alman, STOC’21; Alman, Guan and Padaki, SODA’23; Sergeev’22] has improved on decades-old constructions in this area using a new rebalancing approach, but it was unclear how to apply this approach optimally, and the previous versions had complicated technical requirements.We find that Strassen’s theory of asymptotic spectra can be applied to capture the design of these circuits. This theory was designed to generalize the known techniques behind matrix multiplication algorithms as well as a variety of other algorithms with recursive structure, and it brings a number of new tools to use for designing depth- 2 circuits. In particular, in hindsight, we find that the techniques of recent work on rebalancing were proving special cases of the duality theorem which is central to Strassen’s theory. We carefully outline a collection of obstructions to designing small depth- 2 circuits using a rebalancing approach, and apply Strassen’s theory to show that our obstructions are complete.Using this connection, combined with other algorithmic techniques (including matrix rigidity upper bounds, constant-weight binary codes, and a “hole-fixing lemma” from recent matrix multiplication algorithms), we give new improved circuit constructions as well as other applications, including:•The $N \times N$ disjointness matrix has a depth-2 linear circuit of size $O\left(N^{1.2495}\right)$ over any field. This is the first construction which surpasses exponent 1.25, and thus yields smaller circuits for many families of matrices using reductions to disjointness, including all Kronecker products of $2 \times 2$ matrices, without using matrix rigidity upper bounds.•Barriers to further improvements, including that the Strong Exponential Time Hypothesis implies an $N^{1+\Omega(1)}$ size lower bound for depth-2 linear circuits computing the WalshHadamard transform (and the disjointness matrix with a technical caveat), and that proving such a $N^{1+\Omega(1)}$ depth2 size lower bound would imply breakthrough threshold circuit lower bounds.•The Orthogonal Vectors (OV) problem in moderate dimension d can be solved in deterministic time $\tilde{O}\left(n \cdot 1.155^{d}\right)$, derandomizing an algorithm of Nederlof and Wegrzycki [STOC’21], and the counting problem can be solved in time $\tilde{O}\left(n \cdot 1.26^{d}\right)$, improving an algorithm of Williams [FOCS’24] which runs in time $\tilde{O}\left(n \cdot 1.35^{d}\right)$. We design these new algorithms by noticing that prior algorithms for OV can be viewed as corresponding to depth- 2 circuits for the disjointness matrix, then using our framework for further improvements.

We present an algebraic algorithm that computes the composition of two power series in softly linear time complexity. The previous best algorithms are$\mathrm{O}(n^{1+o(1)})$non-alzebraic algorithm by Kedlaya and Umans (FOCS 2008) and an$\mathrm{O}(n^{1.43})$algebraic algorithm by Neiger, Salvy, Schost and Villard (JACM 2023). Our algorithm builds upon the recent Graeffe iteration approach to manipulate rational power series introduced by Bostan and Mori (SOSA 2021).