Class Meetings: F 2:00pm–3:40pm, Car Barn 205
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.
Textbook:
Although there's no textbook for this course, lecture notes and references for each lecture will be posted during the semester.
Grading:
In order to pass this course, one needs to design a deterministic polynomial-time algorithm that constructs Valiant-rigid matrices for infinitely many values of n.
Disability Disclosure Statement:
If you have a disability that may affect your academic work or well-being and for which accommodations may be necessary, please inform us and contact the
Academic Resource Center.
Religious Observance:
Any student who is unable to attend a class because of the observance of a major religious holiday will be provided with the opportunity to make up for the class.
Title IX:
We are committed to supporting survivors and those impacted by sexual misconduct. For details of University resources, consult Georgetown University
Sexual Misconduct Reference Guide.