Matrix Rigidity

3.0 credits · Graduate

Matrix rigidity, introduced by L. Valiant in 1977, measures the Hamming distance from a given matrix to the set of low rank matrices. This definition might seem strange at first, but in the past 50 years it has revealed curious connections between algebra, geometry, and computation. In this course, we will prove central results on matrix rigidity, and will see its applications to circuit lower bounds, data structures, communication complexity, and information theory. Along the way, we will see beautiful results in neighboring areas, including locally decodable codes, the cap set problem, superconcentrators, and the orthogonal vectors problem.