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. |