The Geometry of Matrix Rigidity

Consider the following problem: Given an n×n matrix A and an input x, compute Ax. This problem has a simple algorithm which runs in time O(n²). The question thus is: Is this is the best possible ? Valiant showed ([12]) that if an n × n matrix A is rigid, then the smallest straight line program computing Ax is either super-linear size, or has super logarithmic depth. Roughly a matrix of rank n is said to be rigid, if to bring its rank down to n/2, one has to change at least n[superscript1+є] of its entries, for some є > 0. After considerable effort by many researchers, the problem of finding an explicit rigid matrix (hence proving circuit lower bounds) remains elusive. This paper casts the problem of matrix rigidity in the language of algebraic geometry. As a first step, we provide the basic setup and prove some elementary results about this problem. This setting facilitates our understanding of the difficulty of determining the rigidity of an explicit matrix (like Hadamard). On the brighter side, we hope that tools from algebraic geometry might eventually help establish rigidity of explicit matrices