High-dimensional Algorithms: Schedule + Readings

Lecture notes (updated frequently)

Aug 23 Course Introduction. Examples of how volume changes with dimension. (K. Ball's intro to modern convex geometry.)
Aug 25 Learning via Sampling. Brunn-Minkowski inequality. (notes; R. Gardner's survey on B-M.)
Aug 30 Maxcut, Sparsest cut, min distortion embeddings. (Chaps 2, 3 from "The Random Projection Method").
Sep 1 Grunbaum's inequality. Convex optimization via Sampling (notes).
Sep 6 Prekopa-Leindler inequality
Sep 13, 15 Rounding. Sandwiching. Isotropic position.
Sep 20, 22 Learning, Convex concepts.
Sep 29 Gaussian Isoperimetry. One-dim localization
Oct 4,6 Volume computation/Integration via Sampling.
Oct 11, 13, 20 Sampling, Isoperimetry
Oct 25 Student Presentation 1: Ying Xiao, sample complexity of covariance estimation.
Oct 27 SP2: Chris Berlind, Agnostic learning of halfspaces.
Nov 1 No class (Ravi Kannan's lecture at 4:30pm)
Nov 3 SP3: Anand Louis, Invariance principles
Nov 8 Near(est) neighbors, Random projection (RP book)
Nov 10 SP4: Liujia Hu, Locality-sensitive hashing
Nov 17 SP5: Arindam Khan, L1 embeddings revisited.
Nov 22 SP6: Tonghoon Suk, Central Limit Theorem for convex bodies.
Nov 29 Shortest Vector Problem, LLL algorithm. (survey on Algorithmic Geometry of Numbers)
Dec 1 Integer Programming (guest lecturer: Karthik).
Dec 6 Misc. topics, open problems.