Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum

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.