CSE 599I: Geometric embeddings and high-dimensional phenomena (WI 2007)

[note: lecture notes for a majority of the missing lectures are forthcoming --3/28/07]

[course description | scribe notes | homeworks | related material]

course description

Instructor: James Lee, CSE 640, tel. 616 4368

Classes are Tuesdays and Thursdays, 10:30-11:50am, CSE 303 (note the new location)

Office hours: By appointment (just send me email or drop by; I'm happy to meet anytime)

Course Requirements: scribing two lectures; homeworks

About this course: Structure preserving maps from one geometric space to another have become a major tool in the development of approximation algorithms for a number of classical NP-hard problems. We will study the theory of such embeddings, as well as some of the most spectacular applications in computer science.

A large component of the course will deal with high-dimensional non-linear geometry and high-dimensional probability; these have become essential tools in the analysis of semi-definite programming relaxations, and in the design of algorithms for high-dimensional search. We'll also look at some Fourier-analytic approaches, and the connections to geometric "rigidity," PCPs, and hardness of approximation.

schedule of classes

Template for lecture notes: template.tex.

  1. January 16 [ps | pdf] Introduction. Metric spaces, normed spaces and geometry of their unit balls. Embeddings and distortion. Every metric space embeds isometrically in Linfinity. [scribe: Alex Jaffe] A video of the 3-dimensional Lp ball morphing from p=2 to p=1, then all the way to p=infinity.

  2. January 18 [ps | pdf] Bourgain's embedding into Euclidean space. [scribe: Ravi Kiran]

  3. January 23 [ps | pdf] Application of Bourgain's embedding to the Sparsest Cut problem and approximate max-flow/min-cut theorems for multi-commodity flows. [scribe: Ning Chen] See also the papers of Linial, London, and Rabinovich and Aumann and Rabani.

  4. January 25 Concentration of Lispchitz functions and vertex expansion; spectral gap and edge-expansion; Poincare inequalities and distortion lower bounds. See the papers of Ledoux and Talagrand to learn more about the concentration of measure phenomenon, the relation to spectral gap, Poincare and log-Sobolev inequalities. [scribe: me]

  5. January 30 Measure concentration on the sphere; the Johnson-Lindenstrauss flattening lemma; dimension reduction with discrete matrices. [scribe: Prasad]

  6. February 1 [ps | pdf] Lower bounds on dimension reduction in L1. [scribe: Dang-Trinh Huynh-Ngoc] The original paper of Brinkman and Charikar and the simpler proof presented in class. A proof of the uniform convexity inequality for Lp spaces.

  7. February 6 Dimension reduction upper bounds for L1: Dominated L1 embeddings [scribe: Xu Miao]

  8. February 8 Dimension reduction upper bounds for L1: Series-parallel graphs [scribe: J. Vincent-Foglesong]

  9. February 13 Random decomposability and the CKR decomposition.

  10. February 15 Random tree embeddings.

  11. February 20 Rao's method and measured descent.

  12. February 22 The scale gluing lemma.

  13. February 27 Volume distortion and graph bandwidth.

  14. March 1 The Arora-Rao-Vazirani algorithm, part I.

  15. March 6 The Arora-Rao-Vazirani algorithm, part II.

  16. March 8 Embedding negative-type metrics into L1.

homeworks

related material