CS496: High-Dimensional Probability in Computer Science

This course covers tools from high-dimensional probability and their applications in theoretical computer science.

Instructor. Sidhanth Mohanty (Email me at sidhanth (dot) mohanty (at) northwestern (dot) edu)

When? 11:00 am to 12:30 pm, Mondays & Wednesdays

Where? Tech M120

Office Hours. TBA; also by appointment

Evaluation. Homeworks and final project

Anonymous feedback. TBA.

March 31	Gaussian Concentration of Measure
April 1	Dimensionality Reduction and Streaming
April 6	Gaussian Comparison Inequalities Chapter 4 of these notes
April 8	Euclidean Sections and Compressed Sensing
April 13	John’s Ellipsoid Theorem
April 15	Dvoretzky’s Theorem
April 20	Optimal Transport I: T2 Inequalities and Concentration Chapter 4.4 of these notes.
April 22	Optimal Transport II: Proof of Gaussian T2 Inequality Problem 4.10 of these notes.
April 27	Brownian Motion I: Martingale Concentration See Theorem 11.7 of these notes.
April 29	Brownian Motion II: Spencer’s Discrepancy Theorem
May 4	Quantitative Invertibility of Random Matrices
May 6	No class (instructor sick)
May 11	TBD
May 13	TBD
May 18	TBD
May 20	TBD
May 25	No class (Memorial Day)
May 27	TBD
June 1	TBD
June 3	TBD
June 8	TBD

TBA