2021/02/24 by Alman, Josh · 1 citation
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2102.11992
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: \bullet For any d> 1, and over any field \mathbbF, the N × N Walsh-Hadamard transform has a depth-d linear circuit of size O(d ⋅ N1 + 0.96/d). This circumvents a known lower bound of Ω(d ⋅ N1 + 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. \bullet The N × N Walsh-Hadamard transform has a linear circuit of size ≤ (1.81 + o(1)) N log2 N, improving on the bound of ≈ 1.88 N log2 N which one obtains from the standard fast Walsh-Hadamard transform. \bullet 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 \mathbbF and any function f : \0,1\n → \mathbbF, the matrix Vf ∈ \mathbbF2n × 2n given by, for any x,y ∈ \0,1\n, Vf[x,y] = f(x \wedge y), and - for any field \mathbbF and any fixed-size matrices M1, …, Mn ∈ \mathbbFq × q, the Kronecker product M1 ⊗ M2 ⊗ ⋯ ⊗ Mn. This generalizes recent results on non-rigidity, using a simpler approach which avoids needing the polynomial method.