Spectral Methods for Matrix Rigidity with Applications to Size-Depth Tradeoffs and Communication Complexity

The rigidity of a matrix measures the number of entries that must be changed in order to reduce its rank below a certain value. The known lower bounds on the rigidity of explicit matrices are very weak. It is known that stronger lower bounds would have implications to complexity theory. We consider weaker forms of the rigidity problem over the complex numbers. Using spectral methods, we derive lower bounds on these variants. We then give two applications of such weaker forms. First, we show that our lower bound on a variant of rigidity implies lower bounds on size-depth tradeoffs for arithmetic circuits with bounded coefficients computing linear transformations (an unconditional result). These bounds generalize a recent result of Nisan and Wigderson. The second application is conditional; we show that it would suffice to prove lower bounds on certain weaker forms of rigidity to conclude several separation results in communication complexity theory. Our results complement and strengthen..