---

* 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 Shoup-Smolensky (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


---

---