Overview

Class Meetings: TBA

Instructor: Alexander Golovnev

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.

Textbooks:

Although there's no textbook for this course, lecture notes and references for each lecture will be posted during the semester.

Grading:

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.

Homework:

We encourage you to use LaTeX for your solutions, an example of a LaTeX source file for homeworks is available here.

Schedule

Class Date Topics References
Part I. Explicit constructions of rigid matrices.
1 - Introduction and course overview. Definition, examples, and applications of matrix rigidity. -
2 - Existence of rigid matrices, explicit and non-explicit matrices. -
3 - Error correcting codes, Friedman's construction of rigid matrices. -
4 - Constructions of Pudlák and Rödl; and Shokrollahi, Spielman, and Stemann. -
Part II. Semi-explicit constructions of rigid matrices.
5 - Shoup-Smolensky dimension, lower bounds for linear circuits. -
6 - Rigid matrices with a few algebraically independent entries. -
7 - Matrix rigidity from algebraic geometry. -
8 - Rigidity of Toeplitz matrices. -
9 - Rigidity of sparse matrices, rigid matrices in sub-exponential time. -
10 - Rigidity in PNP. Tools. -
11 - Rigidity in PNP. Proof. -
Part III. Limitations of known techniques.
12 - Hadamard matrix is not rigid. -
13 - Croot-Lev-Pach lemma, rigidity of matrices M(x,y)=f(x+y). -
14 - Generalized Hadamard, Fourier, and Toeplitz matrices. -
15 - Rigidity of error correcting codes. -
16 - Limitations of combinatorial methods. -
17 - Rigidity of circulant matrices. -
18 - Natural proofs, inapproximability of rigidity. -
Part IV. Applications of rigidity.
19 - Rigidity and circuit lower bounds. -
20 - Rectangular rigidity, explicit constructions. -
21 - Rigidity and data structure lower bounds. -
22 - Rigidity and communication complexity. -
23 - Other notions of rigidity. -
24 - Minrank of a graph, number-on-the-forehead model of multiparty communication, applications to circuit complexity. -
25 - Lower and upper bounds on minrank. -
26 - Open problems. -
27 - Final projects. -

Course Policies

Academic Honesty:

We encourage you to discuss the homework assignments with your classmates, however you must explicitly list all collaborators and materials that you used, and you must write up your own solution to every problem. See Georgetown University Honor System.

Late Submissions:

Late submissions of homework solutions are graded with a 10% penalty per day of late submission.

Laptops:

We discourage the use of laptops as this might be distracting to other students.

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.

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.

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.