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]
| scribe notes
| related material]
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.
- 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.
- January 18
[ps | pdf]
Bourgain's embedding into Euclidean space. [scribe: Ravi Kiran]
- 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.
- 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]
- January 30 Measure concentration on the sphere; the Johnson-Lindenstrauss flattening lemma;
dimension reduction with discrete matrices. [scribe: Prasad]
- February 1
[ps | pdf]
Lower bounds on dimension reduction in L1. [scribe:
The original paper of Brinkman and Charikar and the simpler
proof presented in class.
A proof of the uniform convexity inequality for Lp spaces.
- February 6 Dimension reduction upper bounds for L1: Dominated L1 embeddings
[scribe: Xu Miao]
- February 8 Dimension reduction upper bounds for L1:
[scribe: J. Vincent-Foglesong]
- February 13 Random decomposability and the CKR decomposition.
- February 15 Random tree embeddings.
February 20 Rao's method and measured descent.
February 22 The scale gluing lemma.
February 27 Volume distortion and graph bandwidth.
March 1 The Arora-Rao-Vazirani algorithm, part I.
March 6 The Arora-Rao-Vazirani algorithm, part II.
March 8 Embedding negative-type metrics into L1.
- Homework #1 [ps | pdf] Due Jan 30. Solutions [ps | pdf]
- Homework #2 [ps | pdf] Due Feb 15. Solutions [ps | pdf]
- surveys, open problems, etc.
- courses at other schools