COS 598 I: Matrix Concentration and Applications

Instructor: Pravesh K Kothari

Lectures

Fridays, 1:30-4:20 (CS 104)

Office Hours

After class (4:30-5:30)

Discussion

Join the discussion on Ed

Homeworks

We will have up to 4 graded homeworks in the class (40% of the grade), and a final project (55% of the grade). 5% of the grade will be class participation.

The homeworks should be typeset (preferably using LaTeX) and submitted via Gradescope.

Final Project

Your final project should be a lecture notes style exposition of a topic that fits the theme of the class. It is due by May 6 2025. A few suggested topics (you are free to choose your own) include: 1) Quantum Query Lower Bounds 2) Tensor concentration inequalities , 3) Column subset selection and efficient algorithms for restricted invertibility, 4) More elementary proofs of restricted invertibility 5) Covariance estimation with weak moment control , 6) Sparsifying sums of norms, 7) Progress on the matrix spencer problem.

Class Schedule

Lecture Number Date Topic Notes Scribe
101/31/2025Introduction, the Non-Commutative Khintchine Inequality and Graph SparsificationHandwritten Notes, Scribed NotesKothari
202/07/2025Elementary Proofs of Matrix Khintchine, Bernstein and ChernoffScribed Notes Nilava Metya
302/14/2025Subgaussian Tail BoundsScribed NotesStefan Tudose
402/21/2025No Class
502/28/2025Refuting Random Constraint Satisfaction ProblemsScribed NotesStefan Tudose
603/07/2025Hypergraph Moore BoundScribed NotesStefan Tudose
703/14/2025Spring Break
803/21/2025Locally Decodable Codes and the Restricted k-AP problem
903/28/2025Matrix Completion
1004/04/2025Graph Sparsification via Barrier Methods
1104/11/2025Barrier Methods for Restricted Invertibility
1204/18/2025
1304/25/2025