News
Colloquia
Matrix Rigidity
Satyanarayana Lokam University of Michigan
Thurssday, March 24, 2005
JEC 3117  4:00 p.m. to 5:00 p.m.
Refreshments at 3:30 p.m.
The rigidity of a matrix A is the minimum number of entries of A that must
be changed to reduce its rank to, or below, a specified value r. It is a
major unsolved problem (Valiant, 1977) to construct "explicit" families of
matrices of superlinear rigidity for the rank bound r = cn for some positive
constant c. Such a lower bound has numerous interesting consequences in
computational complexity. We prove an asymptotically optimal Omega (n^2)
lower bound on the rigidity of a "somewhat explicit" family of matrices with
respect to the rank bound r = n/17. The entries of our matrices are the square
roots of distinct prime numbers.
An important consequence of such superlinear lower bounds on rigidity is
superlinear lower bounds on the arithmetic complexity of linear transformations.
We show a nearly optimal Omega((n^2)/log n) lower bound on the arithmetic complexity
of the linear transformation given by the above family of matrices. An algebraic
dimention due to ShoupSmolensky (1997) is used to prove both our rigidity and
circuit lower bounds.
Two challenging candidate matrices for superlinear rigidity and circuit lower bounds
are Hadamard matrices and the Fourier Transform matrices. We will present an overview
of known lower bounds on the rigidity and circuit complexity of the Fourier Transform.
Last updated: March 3, 2005
