18.409 Topics in Theoretical Computer Science
When and where:
The class meets on Mondays and Wednesdays from 9:30 to 11:00 in room
The first lecture will be on Wed Sept 6th.
There will be no class on Monday Oct 23rd (FOCS) and on Monday Oct
Instructor: Michel Goemans, room
Topic: The topic of this course/seminar is on the
embedding of finite metric spaces into normed spaces, and its
applications to algorithmic problems. This is a field with
lots of developments in the last 5 years, and the goal is to cover
some of them.
Format: Lectures will be given by the instructor
(including the first few) as well as by the participants. Participants
will also be expected to take turns to scribe lecture notes.
Syllabus. Here is a very preliminary and very partial list of topics.
- Sparsest cut. Linial, London and Rabinovich, Combinatorica,
- Bourgain's embedding of any n-point metric into Euclidean space
with distortion O(log(n)). Other Frechet embeddings.
Lower bounds for Euclidean embeddings.
- Dimension reduction a la Johnson-Lindenstrauss. Dimension
reduction for other metric spaces.
- Embeddings of planar metrics into Euclidean space. S. Rao,
1999. Matching lower bound: Newman and Rabinovich,
A lower bound on
the distortion of embedding planar metrics into Euclidean space.
- The gluing lemma to combine embeddings at different
scales. J. Lee, Distance
scales, embeddings, and metrics of negative type, full version of
2005 SODA paper.
- Arora, Rao and Vazirani for sparsest cut. Embeddings of negative
type metrics into Euclidean space. S. Arora, J. Lee and A. Naor, Euclidean
distortion and the Sparsest Cut, full version of STOC '05 paper.
- Harmonic analysis and lower bounds for distortion. S. Khot and A. Naor,
- Doubling metrics.
- Probabilistic tree embeddings.
Schedule and Scribed Lecture Notes:
- Wed, Sept 6. Lecture 1. Embedding into linfinity. Dimension for
embedding into lp. l2 embeds into
lp. Notes in
scribed by Punyashloka Biswal.
- Mon, Sept 11. Lecture 2. Characterization of
l2-embeddability. l2-distortion needed for
Hamming metric. General lower bounds for embeddability. Notes in
scribed by David Charlton.
- Wed, Sept 13. Lecture 3. l2-distortion lower bound for
planar graph metrics and expanders. Notes in
scribed by Jelani Nelson.
- Mon, Sept 18. Lecture 4. Sparsest cut, concurrent flows and their
relationship with metric embeddings.
scribed by Kyle Burke.
- Wed, Sept 20. Lecture 5. Bourgain's logarithmic distortion for embedding any
finite metric into l1. Notes in
scribed by Jinwoo Shin.
- Wed, Sept 27. Lecture 6. Dimension reduction for
l2-embeddings. Upper bound (Johnson-Lindenstrauss) and
lower bound (Alon). Notes in
scribed by Benjamin Rossman. For more on measure
concentration, see Barvinok's lecture
- Mon, Oct 2. Lecture 7. Lower bounds for dimension reduction for
l2 (Alon) and l1 (Brinkman
and Charikar, FOCS 2003, and Lee
and Naor). Notes in
scribed by Petar Maymounkov.
- Wed, Oct 4. Lecture 8. Embedding planar graph metrics into
l2 with distortion log1/2 n. Rao, SOCG
'99, see also discussion in Chapter 15 of Matousek.
scribed by Shubhangi Saraf.
- Wed, Oct 11. Lecture 9. Planar graph decomposition a la Klein,
Plotkin, Rao (1993) cont'd. Notes in
scribed by Yingchao Zhao.
- Mon, Oct 16. Lecture 10. Negative type metrics and the sparsest
cut problem. Notes in
scribed by Dan Stratila.
- Wed, Oct 18. Lecture 11. Arora, Rao and Vazirani approximation
algorithm for sparsest cut. Arora et
al. paper. Notes in
scribed by Krzysztof Onak.
- Fri, Oct 20, 4PM in 32G-575. Lecture 12. Presentation by Alex Andoni on the
Khot-Naor use of Fourier analysis for lower bounds.
- Mon, Oct 23. No lecture (FOCS).
- Wed, Oct 25. Lecture 13. Arora, Rao and Vazirani (cont'd). See
also Section 4 of Lee
for the main argument.
- Mon, Oct 30. No lecture.
- Wed, Nov 1st. Lecture 14. Presentation by Hoda Bidkhori and Amanda Epping
Redlich on Bartal's paper
about probabilistic embeddings of metrics into tree
- Mon, Nov 6th. Lecture 15. Presentation by Alex Andoni in ps
or in pdf
on the edit metric and the lower bound of Krauthgamer and Rabani, Improved
lower bounds for embeddings into L1, SODA, 2006.
- Wed, Nov 8th. Lecture 16. Presentation by Adriana Lopez and
Shubhangi Saraf in ps
or in pdf
on Lipschitz embeddings and embedding sphere metrics into the plane.
- Mon, Nov 13th. Lecture 17. Presentation by Kyomin Jung and Jin
Woo Shin on Feige's volume preserving embeddings.
- Wed, Nov 15th. Lecture 18. Feige's volume preserving embeddings
cont'd. And beginning of the presentation by Krzysztof Onak and David
Sontag (to be cont'd).
- Mon, Nov 20th. Lecture 19. Presentation by Krzysztof Onak and
David Sontag in ps
or in pdf
Embeddings with Relaxed Guarantees.
- Wed, Nov 22nd. Lecture 20. Presentation by Michael Manapat in ps
or in pdf
on Lee's gluing of
embeddings at different scales.
- Mon, Nov 27th. Lecture 21. Gluing continued (proofs by Michel
Goemans). Scribed notes by Adriana Lopez.
- Wed, Nov 29th. Lecture 22. Presentation by Punya Biswal and
Jelani Nelson in ps or pdf
on Gupta, Newman, Rabinovich, Sinclair's result on
embedding series-parallel graph metrics into l1.
- Mon, Dec 4th. Lecture 23. Presentation by Juliane Dunkel and Dan
Stratila on doubling metrics (paper by Gupta, Krauthgamer and Lee).
- Wed, Dec 6th. Lecture 24. Presentation by Petar Maymounkov on
Embeddings of Graph metrics into Random Trees by Dhamdere, Gupta
- Mon, Dec 11th. Lecture 25. Presentation by Tasos Siridopoulos on
Kakcharoenphol, Rao and Talwar's O(log n) probabilistic embeddings
into dominating trees.
- Wed, Dec 13th. Lecture 26. Presentation by Kyle Burke and David
Charlton on the tradeoff between dimension and distortion. See