Sorry, an error occurred while loading the content.

## [Computational Complexity] Matrix Rigidity

Expand Messages
• 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
Message 1 of 1 , Jul 6, 2005
• 0 Attachment
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

Your message has been successfully submitted and would be delivered to recipients shortly.