Smaller Low-Depth Circuits for Kronecker Powers

Download PDF

We give new, smaller constructions of constant-depth linear circuits for computing any matrix which is the Kronecker power of a fixed matrix. A standard argument (e.g., the mixed product property of Kronecker products, or a generalization of the Fast Walsh-Hadamard transform) shows that any such N \times N matrix has a depth-2 circuit of size O(N^{1.5}). We improve on this for all such matrices, and especially for some such matrices of particular interest:
- For any integer q > 1 and any matrix which is the Kronecker power of a fixed q \times q matrix, we construct a depth-2 circuit of size O(N^{1.5 - a_q}), where a_q > 0 is a positive constant depending only on q. No bound beating size O(N^{1.5}) was previously known for any q>2.
- For the case q=2, i.e., for any matrix which is the Kronecker power of a fixed 2 \times 2 matrix, we construct a depth-2 circuit of size O(N^{1.446}), improving the prior best size O(N^{1.493}) [Alman, 2021].
- For the Walsh-Hadamard transform, we construct a depth-2 circuit of size O(N^{1.443}), improving the prior best size O(N^{1.476}) [Alman, 2021].
- For the disjointness matrix (the communication matrix of set disjointness, or equivalently, the matrix for the linear transform that evaluates a multilinear polynomial on all 0/1 inputs), we construct a depth-2 circuit of size O(N^{1.258}), improving the prior best size O(N^{1.272}) [Jukna and Sergeev, 2013].
Our constructions also generalize to improving the standard construction for any depth \leq O(\log N). Our main technical tool is an improved way to convert a nontrivial circuit for any matrix into a circuit for its Kronecker powers. Our new bounds provably could not be achieved using the approaches of prior work.