Spectral Methods for Matrix Rigidity with Applications to Size–Depth Trade-offs 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 important consequences in complexity theory. We consider some restricted variants of the rigidity problem over the complex numbers. Using spectral methods, we derive lower bounds on these variants. Two applications of such restricted variants are given. First, we show that our lower bound on a variant of rigidity implies lower bounds on size–depth trade-offs for arithmetic circuits with bounded coefficients computing linear transformations. These bounds generalize a result of Nisan and Wigderson. The second application is conditional; we show that it would suffice to prove lower bounds on certain restricted forms of rigidity to conclude several separation results such as separating the analogs of PH and PSPACE in the model of two-party communication complexity. Our results complement and strengthen a result of Razborov.  We introduce a combinatorial complexity measure, called AC0-dimension, of sets of Boolean functions. While high rigidity implies large AC0-dimension, large AC0-dimension for explicit sets would already give explicit languages outside the analog of PH in two-party communication complexity. Moreover, the concept of AC0-dimension allows us to formulate interesting combinatorial problems which may be easier than rigidity and which would still have consequences to separation questions in communication complexity.