Instructor: Pravesh K Kothari
Fridays, 1:30-4:20 (CS 104)
After class (4:30-5:30)
Join the discussion on Ed
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.
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.
| Lecture Number | Date | Topic | Notes | Scribe |
|---|---|---|---|---|
| 1 | 01/31/2025 | Introduction, the Non-Commutative Khintchine Inequality and Graph Sparsification | Handwritten Notes, Scribed Notes | Kothari |
| 2 | 02/07/2025 | Elementary Proofs of Matrix Khintchine, Bernstein and Chernoff | Scribed Notes | Nilava Metya |
| 3 | 02/14/2025 | Subgaussian Tail Bounds | Scribed Notes | Stefan Tudose |
| 4 | 02/21/2025 | No Class | ||
| 5 | 02/28/2025 | Refuting Random Constraint Satisfaction Problems | Scribed Notes | Stefan Tudose |
| 6 | 03/07/2025 | Hypergraph Moore Bound | Scribed Notes | Stefan Tudose |
| 7 | 03/14/2025 | Spring Break | ||
| 8 | 03/21/2025 | Locally Decodable Codes and the Restricted k-AP problem | ||
| 9 | 03/28/2025 | Low-Rank Matrix Completion | ||
| 10 | 04/04/2025 | Graph Sparsification via Barrier Methods | ||
| 11 | 04/11/2025 | Barrier Methods for Restricted Invertibility | ||
| 12 | 04/18/2025 | The BBvH Inequality and Matrix Spencer Problem | ||
| 13 | 04/25/2025 | The BBvH Matrix Concentration Inequality |