Description: 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 40 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.
Prerequisites: Although there are no formal prerequisites for this course, we expect familiarity with mathematical proofs, elementary complexity theory, discrete mathematics, linear algebra, and probability theory.
Although there's no textbook for this course, lecture notes and references for each lecture will be posted during the semester.
Grading will be based on three homework problem sets (50%), and a final project (50%). The final project could be a research result related to the topic of the class, or a survey of a related topic not covered in class.
We encourage you to use LaTeX for your solutions, an example of a LaTeX source file for homeworks is available here