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	Random Graphs: Clique Number in $\mathrm{G}(n,1/2)$
May 13	Sparse Random Graphs: Giant Component Threshold
May 18	Random CSPs and SAT thresholds
May 20	Markov Chain Monte Carlo
May 25	No class (Memorial Day)
May 27	Probabilistic Method Independent sets in bounded degree graphs Weierstrass polynomial approximation theorem
June 1	Fourier Analysis and Property Testing
June 3	Semidefinite Programming and Max Cut

Due Date: June 10