Fall 2014

Matrix Rigidity

Thursday, September 4th, 2014, 1:30 pm3:00 pm

Add to Calendar


Calvin Lab Auditorium

This lecture will be a survey on Matrix Rigidity. The rigidity of a matrix A for a target rank r is the minimum number of entries of A that must be changed to ensure the altered matrix has rank at most r. The notion of matrix rigidity was introduced by Valiant (1977) as a means to proving lower bounds on the arithmetic complexity of linear transformations. In particular, he showed that if an n × n matrix has rigidity n1 for a target rank δn (where ε and δ are positive constants), then the map x → Ax cannot be computed by linear size log-depth circuits whose gates compute linear combinations of their inputs. Proving such a lower bound on explicit families of matrices still remains a challenging open problem. In this lecture, we will

  • Introduce matrix rigidity and motivate the problem of proving lower bounds.
  • Prove rigidity lower bounds for explicit matrices, especially over finite fields. These bounds are limited to Ω( ( n2 ⁄ r ) log ( n ⁄ r ) ).
  • Prove rigidity lower bounds using algebraic dimension arguments, especially over complex numbers. This approach yields strong bounds, e.g., Ω(n2), for certain non-explicit matrices.
  • Describe other notions of rank robustness with applications in computational complexity.

We will outline general approaches to the rigidity problem in the results mentioned above and state several open questions along the way.

PDF icon Matrix Rigidity (Exercises)151.11 KB