Description: This course covers fundamental techniques and a range of mathematical tools that underlie today’s research in theoretical computer science and are essential knowledge for students pursuing research in theoretical computer science or machine learning theory. The course targets current graduate and undergraduate students interested in pursuing research in these areas. Topics will be chosen from four core areas: 1) Concentration Inequalities and their Applications. 2) Selected Topics in Convex Analysis and Optimization. 3) Foundations of Spectral Methods. 4) Discrete Fourier Analysis. Depending on student interest, additional topics will be chosen. The topics may include applied analysis for learning theory, coding theory, probabilistic proofs, graph algorithms, and sampling.
Time/Location: TTH 3:00 PM - 4:15 PM at HAAS G066
Instructor: Ruizhe Zhang Office hours: by appointment only
Teaching Assistant: Xiuyu Ye Office hours: 10:30 AM - 11:30 AM at DSAI B055
Course policy: See syllabus for detailed overview.
The schedule will be updated as we progress through the course.
| Date | Topic | Materials | Resources |
|---|---|---|---|
| Jan 13 | Introduction | [slides] |
|
| Jan 15 | No lecture | ||
| Jan 20 | Mathematical Basics | ||
| Jan 22 | Concentration inequalities (I): Markov inequality and Chebyshev inequality | ||
| Jan 27 | Concentration inequalities (II): Chernoff bounds | ||
| Feb 3 | Concentration inequalities (III): McDiarmid’s Inequality | ||
| Feb 5 | Convex geometry and analysis (I) | ||
| Feb 10 | Convex geometry and analysis (II) | ||
| Feb 12 | Convex geometry and analysis (III): Isoperimetric inequalities, localization, and the KLS conjecture | ||
| Feb 17 | Convex optimization (I): Gradient descent | ||
| Feb 19 | Convex optimization (II): Polynomial approximation | ||
| Feb 24 | Spectral methods (I): Basics | ||
| Feb 26 | Spectral methods (II): Markov chains | ||
| Mar 3 | Spectral methods (III): Matrix perturbation theory | ||
| Mar 5 | Matrix concentration inequalities (I) | ||
| Mar 10 | Matrix concentration inequalities (II) | ||
| Mar 12 | Boolean function analysis (I): Basics of discrete Fourier analysis | ||
| Mar 24 | Boolean function analysis (II): Linearity testing | ||
| Mar 26 | Boolean function analysis (III): Degree, query complexity, and sensitivity | ||
| Mar 31 | Boolean function analysis (IV): Degree, query complexity, and sensitivity | ||
| Apr 2 | Boolean function analysis (V): Isoperimetric inequalities over the hypercube | ||
| Apr 7 | Boolean function analysis (VI): Isoperimetric inequalities over the hypercube | ||
| Apr 9 | Special topics (I) | ||
| Apr 14 | Special topics (II) | ||
| Apr 16 | Special topics (III) | ||
| Apr 21 | Special topics (IV) | ||
| Apr 23 | Project presentations | ||
| Apr 28 | Project presentations | ||
| Apr 30 | Project presentations |