Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909794540978176 |
|---|---|
| author | Alman, Josh Li, Baitian |
| author_facet | Alman, Josh Li, Baitian |
| contents | 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 $\tilde{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 $\tilde{O}(n \cdot 1.26^d)$, improving an algorithm of Williams [FOCS'24] which runs in time $\tilde{O}(n \cdot 1.35^d)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_14489 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum Alman, Josh Li, Baitian Data Structures and Algorithms Computational Complexity 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 $\tilde{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 $\tilde{O}(n \cdot 1.26^d)$, improving an algorithm of Williams [FOCS'24] which runs in time $\tilde{O}(n \cdot 1.35^d)$. |
| title | Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2509.14489 |