Papers
arxiv:2509.14489

Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum

Published on Sep 17, 2025
Authors:
,

Abstract

We study circuits for computing depth-2 linear transforms defined by Kronecker power matrices. Recent works have improved on decades-old constructions in this area using a new ''rebalancing'' approach [Alman, Guan and Padaki, SODA'23; Sergeev'22], but it was unclear how to apply this approach optimally. We find that Strassen's theory of asymptotic spectra can be applied to capture the design of these 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, 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(N^{1.2495}) over any field. This also yield smaller circuits for many families of matrices using reductions to disjointness. - The Strong Exponential Time Hypothesis implies an N^{1 + Ω(1)} size lower bound for depth-2 linear circuits computing the Walsh--Hadamard transform (and the disjointness matrix with a technical caveat), and proving a N^{1 + Ω(1)} depth-2 size lower bound would also imply breakthrough threshold circuit lower bounds. - The Orthogonal Vectors (OV) problem in moderate dimension d can be solved in deterministic time O(n cdot 1.155^d), derandomizing an algorithm of Nederlof and Węgrzycki [STOC'21], and the counting problem can be solved in time O(n cdot 1.26^d), improving an algorithm of Williams [FOCS'24] which runs in time O(n cdot 1.35^d).

Community

Sign up or log in to comment

Get this paper in your agent:

hf papers read 2509.14489
Don't have the latest CLI?
curl -LsSf https://hf.co/cli/install.sh | bash

Models citing this paper 0

No model linking this paper

Cite arxiv.org/abs/2509.14489 in a model README.md to link it from this page.

Datasets citing this paper 1

Spaces citing this paper 0

No Space linking this paper

Cite arxiv.org/abs/2509.14489 in a Space README.md to link it from this page.

Collections including this paper 0

No Collection including this paper

Add this paper to a collection to link it from this page.