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 ๐ฝ, 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 โ by Pudlรกk (2000), 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.88 N 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 ๐ฝ and any function f : {0,1}^n โ๐ฝ, the matrix V_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 ๐ฝ and any fixed-size matrices M_1, โฆ, M_n โ๐ฝ^q ร q, the Kronecker product M_1 โ M_2 โโฏโ M_n. This generalizes recent results on non-rigidity, using a simpler approach which avoids needing the polynomial method.
READ FULL TEXT