Questions about computing matrix rigidity
The following additional references on Matrix Rigidity may be helpful:


Complexity Lower Bounds using Linear Algebra, S. V. Lokam,
in Foundations and Trends in Theoretical Computer Science, Volume 4, 1-2, 2009.
http://dx.doi.org/10.1561/0400000011 
Using Elimination Theory to construct Rigid Matrices, A. Kumar, S.V. Lokam,. V. Patankar, J. Sarma, 
ECCC TR09-106, http://eccc.hpi-web.de/report/2009/106/