Roughly a matrix of rank $n$ is said to be rigid, if to bring its rank down to $\frac{n}{2}$, one has to change at least $n^{1+\epsilon}$ of its entries, for some $\epsilon > 0$.If an $n \times n$ matrix $A$ is rigid, then the smallest straight line program computing $Ax$  ($x$ is a vector of size $n$) is either super-linear size, or has super logarithmic depth.Is there a converse to the above statement?In other words are there uses to non-trivial and non-obvious low rigidity matrices of full rank in TCS?Is there a notion of rigidity for matrices with lower ranks (say $\frac{n}{c}$ for some constant $c$)?
Matrix rigidity and uses of matrices with low rigidity
cc.complexity theory