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 2-102. The first lecture will be on Wed Sept 6th. There will be no class on Monday Oct 23rd (FOCS) and on Monday Oct 30th.

Instructor: Michel Goemans, room 2-351.

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

Syllabus. Here is a very preliminary and very partial list of topics.

• Sparsest cut. Linial, London and Rabinovich, Combinatorica, 1995.
• 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, 2005.
• Doubling metrics.
• Probabilistic tree embeddings.

Problem Sets:

• Problem set 1.
• The analysis described in the scribed lecture notes of a course at CMU and in an identical set of notes from a course at Chicago has a fatal flaw. Find it!

Schedule and Scribed Lecture Notes:

• Wed, Sept 6. Lecture 1. Embedding into l_infinity. Dimension for embedding into l_p. l₂ embeds into l_p. Notes in ps or pdf scribed by Punyashloka Biswal.
• Mon, Sept 11. Lecture 2. Characterization of l₂-embeddability. l₂-distortion needed for Hamming metric. General lower bounds for embeddability. Notes in ps or pdf scribed by David Charlton.
• Wed, Sept 13. Lecture 3. l₂-distortion lower bound for planar graph metrics and expanders. Notes in ps or pdf scribed by Jelani Nelson.
• Mon, Sept 18. Lecture 4. Sparsest cut, concurrent flows and their relationship with metric embeddings. Notes in ps or pdf scribed by Kyle Burke.
• Wed, Sept 20. Lecture 5. Bourgain's logarithmic distortion for embedding any finite metric into l₁. Notes in ps or pdf scribed by Jinwoo Shin.
• Wed, Sept 27. Lecture 6. Dimension reduction for l₂-embeddings. Upper bound (Johnson-Lindenstrauss) and lower bound (Alon). Notes in ps or pdf scribed by Benjamin Rossman. For more on measure concentration, see Barvinok's lecture notes.
• Mon, Oct 2. Lecture 7. Lower bounds for dimension reduction for l₂ (Alon) and l₁ (Brinkman and Charikar, FOCS 2003, and Lee and Naor). Notes in ps or pdf scribed by Petar Maymounkov.
• Wed, Oct 4. Lecture 8. Embedding planar graph metrics into l₂ with distortion log^1/2 n. Rao, SOCG '99, see also discussion in Chapter 15 of Matousek. Notes in ps or pdf scribed by Shubhangi Saraf.
• Wed, Oct 11. Lecture 9. Planar graph decomposition a la Klein, Plotkin, Rao (1993) cont'd. Notes in pdf scribed by Yingchao Zhao.
• Mon, Oct 16. Lecture 10. Negative type metrics and the sparsest cut problem. Notes in ps or pdf scribed by Dan Stratila.
• Wed, Oct 18. Lecture 11. Arora, Rao and Vazirani approximation algorithm for sparsest cut. Arora et al. paper. Notes in ps or pdf 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 metrics.
• 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 L₁, 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 on Metric 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 l₁.
• 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 Improved Embeddings of Graph metrics into Random Trees by Dhamdere, Gupta and Raecke.
• 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 Matousek's chapter.

References/links:

• A revised and extended Chapter 15 of "Lectures on Discrete Geometry" by Jiri Matousek. Updated bibliography.
• Open problems by Jiri Matousek, updated Sept. 2005.
• Other similar courses have been offered at CMU, Stanford, Chicago, Toronto and Hebrew University.