Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum

We study circuits for computing linear transforms defined by Kronecker power matrices. Depth-2 circuits are central because (1) all known low-depth constructions (e.g., the fast Walsh–Hadamard transform and Yates’ algorithm) can be derived from them, and (2) small depth-2 circuits can yield fast algorithms for Orthogonal Vectors (OV) problem, extending and generalizing a framework initiated by Williams (2024). I’ll begin by introducing recent progress (Jukna–Sergeev 2013; Alman 2021; Alman–Guan–Padaki 2023; Sergeev 2022), which improved decades-old circuit constructions using a "rebalancing" approach. This technique iteratively combines several depth-2 circuits into one more balanced construction, but its optimal use had remained unclear and previous versions relied on intricate technical constraints. Then I’ll briefly review Strassen’s duality theory of asymptotic spectra, and explain how this theory provides a clean unifying perspective. In this framework, rebalancing naturally appears as an instance of Strassen’s duality theorem. We use this connection to fully characterize the obstructions to improving depth-2 constructions, show these obstructions are complete. This allows us to simplify the analyses in previous works, and obtain improved upper bound of depth-2 circuits of disjointness matrices. Based on joint work with Josh Alman.