Overview

Class Meetings: MW 9:30am–10:45am

Office Hours:      M 10:45am–11:45am

Instructor: Sasha 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 Topic Slides Notes References
Part I. Explicit constructions of rigid matrices.
1 08/26 Introduction and course overview. Definition, examples, and applications of matrix rigidity. Slides Notes [Val77], [Vio09, Sec 3.2]
2 08/31 Rigidity and circuits, existence of rigid matrices. Slides Notes [Val77], [Vio09, Sec 3.2]
Homework 1
3 09/02 Explicit and non-explicit matrices. Slides Notes [PR94], [RBG01]
4 09/07 Error correcting codes, Friedman's rigidity lower bound. Slides Notes [Fri93]
5 09/09 Lower Bounds of Pudlák and Rödl; and Shokrollahi, Spielman, and Stemann. Slides Notes [PR94], [SSS97]
6 09/14 Rigidity of Hadamard. Slides Notes [dW06], [Lok95]
7 09/16 Overview of tools used in Part I. Slides Notes
8 09/21 Overview of tools used in Part I. Slides Notes
Part II. Semi-explicit constructions of rigid matrices.
9 09/23 Shoup-Smolensky dimension, rigid matrices with a few algebraically independent entries. Slides Notes [Lok00]
10 09/28 Rigidity and circuit lower bounds for matrices with linearly independent entries. Slides Notes [Lok06], [SS91]
11 09/30 Discussion of project topics. Slides Notes
12 10/05 Hankel matrices and their rigidity. Slides Notes [GT16]
13 10/07 Rigidity of Hankel matrices. Slides Notes [GT16]
14 10/12 Rigidity in sub-exponential time, rigidity of sparse matrices. Slides Notes
15 10/14 Orthogonal vectors. Slides Notes [CW16], [AC19]
16 10/19 Hierarchy Theorems. Slides Notes [Žák83], [AB09, Sec 3]
17 10/21 Rectangular PCPs. Slides Notes [AB09, Sec 11], [BHPT20]
18 10/26 Rigidity in PNP. Slides Notes [AC19], [BHPT20]
Homework 2
Part III. Limitations of known techniques.
19 10/28 Limitations of combinatorial methods. Slides Notes [Lok00], [Val75]
20 11/02 Rigidity of error correcting codes. Slides Notes [Dvi16]
21 11/04 Hadamard matrix is not rigid. Slides Notes [AW17]
22 11/09 Croot-Lev-Pach lemma, rigidity of matrices M(x,y)=f(x+y). Slides Notes [DE17]
23 11/11 Rigidity of Hadamard, Fourier, and Toeplitz matrices. Slides Notes [DL19]
24 11/16 Natural proofs, inapproximability of rigidity. Slides [RR94], [Ale03]
25 11/18 Rigidity of a family of circulant matrices. Slides [CPR98], [GH20]
Part IV. Applications of rigidity.
26 11/30 Rigidity and circuit lower bounds. Slides - [AW17], [GKW21]
27 12/03 Rigidity and data structure lower bounds. Slides - [DGW19], [RR20]
28 12/07 Rigidity and communication complexity. Slides - [Raz89], [Wun12]
29 12/14 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.