Kronecker products, low-depth circuits, and matrix rigidity

For a matrix M and a positive integer r, the rank r rigidity of M is the smallest number of entries of M which one must change to make its rank at most r. There are many known applications of rigidity lower bounds to a variety of areas in complexity theory, but fewer known applications of rigidity upper bounds. In this paper, we use rigidity upper bounds to prove new upper bounds in a few different models of computation. Our results include: • For any d > 1, and over any field F, the N × N Walsh-Hadamard transform has a depth-d linear circuit of size O(d • N 1+0.96/d ). This circumvents a known lower bound of Ω(d • N 1+1/d ) for circuits with bounded coefficients over C [Pud00], by using coefficients of magnitude polynomial in N . Our construction also generalizes to linear transformations given by a Kronecker power of any fixed 2 × 2 matrix. • The N × N Walsh-Hadamard transform has a linear circuit of size ≤ (1.81 + o(1))N log 2 N , improving on the bound of ≈ 1.88N log 2 N which one obtains from the standard fast Walsh-Hadamard transform. • A new rigidity upper bound, showing that the following classes of matrices are not rigid enough to prove circuit lower bounds using Valiant's approach: for any field F and any function f : 0, 1 n → F, the matrix V f ∈ F 2 n ×2 n given by, for any x, y ∈ 0, 1 n , V f [x, y] = f (x ∧ y), and for any field F and any fixed-size matrices M 1 , . . . , M n ∈ F q×q , the Kronecker product This generalizes recent results on non-rigidity, using a simpler approach which avoids needing the polynomial method. • New connections between recursive linear transformations like Fourier and Walsh-Hadamard transforms, and circuits for matrix multiplication.