[Computational Complexity] Matrix Rigidity
Nanda Raghunathan points me to a new paper by Gatis Midrijanis giving a simple proof of the best known rigidity lower bounds for the Sylvester matrices.
The rigidity of a matrix M is a function RM(r) equal to the minimum number of entries of M that you need to change in order to reduce the rank to r. Strong rigidity bounds would have applications for circuit and communication complexity.
Let N=2n. We define the N×N Sylvester S by labeling the rows and columns by n-bit vectors and let si,j=(-1)i·j.
Theorem: If r ≤ N/2 is a power of 2 then RS(r) ≥ N2/4r.
Proof: Divide S uniformly into (N/2r)2 submatrices of size 2r×2r. One can easily verify these submatrices each have full rank. So we need to change at least r elements of each submatrix to reduce each of their ranks to r, a necessary condition to reducing the rank of S to r. QED
This proof works for any matrix whose submatrices have full rank. Consider the N×N matrix B where bi,j=1 if i ≡ j (mod 2r) and 0 otherwise. By the same proof RB(r)=N2/4r even though the rank of B is only 2r.
The moral of this story: We conjecture that the Sylvester matrices have very high rigidity but we still lack the tools that make full use of the structure of these matrices.
Posted by Lance to Computational Complexity at 7/06/2005 09:15:00 AM