CS 6806

Matrix Rigidity

Course Description

Course information provided by the 2026-2027 Catalog.

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.

Last 4 Terms Offered (None)

Learning Outcomes

• Identify the rigidity parameters of explicit, semi-explicit, and non-explicit matrix constructions.
• Analyze major proof techniques for matrix rigidity lower and upper bounds.
• Demonstrate how matrix rigidity results can be applied to problems in computational complexity.

View Enrollment Information