**Instructor:** Tim
Roughgarden (Gates 462)

**Time/location:**
11AM-12:15 PM on Mondays and Wednesdays in Gates B8.

**Course description:**
Sample topics: low-distortion embeddings of finite metrics into L_1, L_p,
and distributions of trees; dimensionality reduction;
volume-respecting embeddings; applications to graph partitioning,
online algorithms, network design, and nearest neighbor search.
Prerequisites: CS261 or comparable mathematical maturity.

**Course overview:**

- Introduction (1 lecture).
- Probabilistic tree embeddings, applications to network design (3-4 lectures).
- Embeddings into L_2 and L_1, applications to multicommodity flows and cuts (3-4 lectures).
- Dimensionality reduction in L_1 and L_2, with applications (1-2 lectures).
- Growth-restricted metrics, notions of dimension, applications to nearest neighbor search and/or beacon-based embeddings. (1-3 lectures).
- Embeddings of other important classes of metrics (e.g. edit distance) (0-2 lectures).
- Volume-respecting embeddings, with applications to bandwidth (0-1 lectures).
- Embeddings of L_2^2, with connections to semidefinite programming and sparest cuts (4 lectures).

**General references on metric embeddings:**

- Chapter 15
of the book Lectures on Discrete
Geometry, by Jiri Matousek.
**Note:**The above link is to a revised September 2005 version of the chapter that includes significantly more material than the previous online version or the actual book chapter.

- Scribe notes from a CMU course taught in Fall 2003 by Anupam Gupta and R. Ravi.
- A handbook chapter by Piotr Indyk and Jiri Matousek.
- A survey paper and talk from FOCS 2001 by Piotr Indyk.

**Detailed schedule and references:**

- Wed 1/11: Introduction: Concave-cost network design and
graph partitioning.
- Relevant reading: Section 15.1 of the Matousek chapter, scribes notes from Gupta/Ravi course (first two lectures plus first section of third lecture).

- Mon 1/16: No class (MLK Jr. Day).
- Wed 1/18: Introduction to probabilistic tree embeddings.
Bartal's (first) theorem achieving O(log^2 n) max expected stretch.
For expository coverage of tree embeddings and Bartal's theorem, see:
- Lectures 8 and 9 from the Gupta/Ravi course;
- Fakcharoenphol/Rao/Talwar, Approximating Metrics by Tree Metrics (survey), SIGACT News 2004;
- Shmoys/Williamson, "Cuts and Metrics" chapter from a forthcoming book on Approximation Algorithms (contact instructor for a copy).

- N. Alon, R.M. Karp, D. Peleg and D. West, A Graph-Theoretic Game and its Application to the k-Server Problem, SIAM J. on Computing, 24, (1995), 78-100;

- Y. Bartal, Probabilistic Approximation of Metric Spaces and its Algorithmic Applications, FOCS '96.

- Mon 1/23: The FRT theorem: optimal probabilistic tree embeddings.
See the surveys from last lecture, and also the original paper
is quite readable:
- Fakcharoenphol/Rao/Talwar, A tight bound on approximating arbitrary metrics by tree metrics, STOC '03/JCSS '04.

- Wed 1/25: Algorithmic applications of probabilistic
tree embeddings. The general result about removing Steiner
nodes from a tree metric while preserving all distances to
within a factor of 8 is from
- A. Gupta, Steiner nodes in Trees don't (really) help, SODA '01.

- B. Awerbuch and Y. Azar, Buy-at-bulk network design, FOCS '97.

- M. Charikar, C. Chekuri, A. Goel, S. Guha and S. Plotkin, Approximating a Finite Metric by a Small Number of Tree Metrics, FOCS '98;

- N. Garg, G. Konjevod, and R. Ravi, A polylogarithmic approximation algorithm for the group Steiner tree problem , SODA '98 and J. Algorithms 2000;
- E. Halperin and R. Krauthgamer, Polylogarithmic inapproximability, STOC '03;

- J. Kleinberg and E. Tardos, Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields, FOCS '99/JACM '02.

- Mon 1/30: Probabilistic embedding of a graph into
one of its spanning trees with maximum expected stretch O(log^2 n).
Reference:
- K. Dhamdhere, A. Gupta, and H. Raecke, Improved Embeddings of Graph Metrics into Random Trees, SODA '06.

- M. Elkin, Y. Emek, D. Spielman, and S. Teng, Lower-Stretch Spanning Trees, STOC '05.

- Wed 2/1: Finish DGR algorithm and analysis.
- Mon 2/6:
Preliminaries about L_1 metrics.
Bourgain's theorem (embedding arbitrary metrics into
L_1 with O(log n) distortion) via the FRT theorem.
Intro to the max concurrent flow and sparsest cut problems.
Bourgain's Theorem originally appeared in
- J. Bourgain, On Lipschitz embedding of finite metric spaces in Hilberg space, Israel Journal of Mathematics, 52:46-52, 1985.

- Wed 2/8: Matching upper and lower bounds (of O(log n)) for the
sparsest cut/maximum concurrent flow gap in general graphs with
general demands. Application of sparsest cut to approximate
balanced cuts.
References:
- The upper bound is due independently to
- Linial/London/Rabinovich, The Geometry of Graphs and Some of Its Algorithmic Applications, FOCS '94/Combinatorica '95; and
- Aumann/Rabani, An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithms, SIAM Journal of Computing '98.

- See also scribe notes from Lecture 6 of the Gupta/Ravi course.
- The lower bound and the application to balanced cuts are from Leighton/Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, FOCS '88/JACM '99.

- The upper bound is due independently to
- Mon 2/13: Frechet embeddings; original proof of Bourgain's
theorem (O(log n) distortion for embedding n-point metrics into L_p,
any 1 <= p < \infty).
High-level idea for Rao's theorem (embedding planar metrics into
L_1 and L_2 with O(\sqrt{log n}) distortion). References:
- This stronger version of Bourgain's theorem and the proof are from the original '85 paper above.
- Highly recommended reading: Sections 15.7 and 15.8 from the Matousek chapter.

- Wed 2/15: Proof of Rao's theorem.
- Rao's theorem in from Rao, Small distortion and volume preserving embeddings for planar and Euclidean metrics, SCG '99.
- See pp.407-410 of the Matousek chapter for a good high-level overview.
- The KPR decomposition theorem (which we may cover in more detail later) is from Klein/Plotkin/Rao, Planar graphs, multicommodity flow, and network decomposition, STOC '93.
- A more recent, refined version of this decomposition is due to Fakcharoenphol/Talwar, An improved decomposition theorem for graphs excluding a fixed minor, APPROX '03.

- Even though series-parallel graphs (let alone planar) graphs cannot be embedded into Euclidean space with better than O(\sqrt{\log n}) distortion (see the 2/27 lecture below), they can be embedded into l_1 with O(1) distortion: Gupta/Newman/Rabinovich/Sinclair, Cuts, trees and l_1-embeddings of graphs, FOCS '99/Combinatorica '04.
- So can k-outerplanar graphs for fixed k: Chekuri/Gupta/Newman/Rabinovich/Sinclair, Embedding k-Outerplanar Graphs into l_1, SODA '03.

- Mon 2/20: No class (Presidents' Day).
- Wed 2/22: Dimensionality reduction in L_2 (Johnson-Lindenstrauss);
embedding L_2 isometrically into L_1.
- Main reference: lectures 15 and 16 from the Gupta/Ravi course.
- For a long list of applications, see Section 3 of the Indyk FOCS '01 survey above.
- The JL lemma is originally from Johnson/Lindenstrauss, Extensions of Lipschitz mappings into a Hilbert space, Contemporary Mathematics, 1984.
- The version using independent Gaussians is from Indyk/Motwani, Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality, STOC '98.
- See also Dasgupta/Gupta, An elementary proof of a theorem of Johnson and Lindenstrauss, Random Structures and Algorithms '03.
- For a version that uses only -1/+1 random variables, see Achlioptas, Database-friendly Random Projections: Johnson-Lindenstrauss with Binary Coins, PODS '01/JCSS '03.

- Mon 2/27: Lower bounds for Euclidean embeddings: Enflo's theorem,
the diamond graphs, and the optimality of Rao's theorem.
- Main reference: Section 15.4 of the Matousek chapter.
- The diamond graphs were introduced in Gupta/Newman/Rabinovich/Sinclair, Cuts, trees and l_1-embeddings of graphs, FOCS '99/Combinatorica '04. In this paper, they were used to show that the FRT theorem is tight even for series-parallel graphs (i.e., probabilistic tree embeddings must incur \Omega(\log n) max expected stretch for such graphs).
- In Newman/Rabinovich, A lower bound on the distortion of embedding planar metrics into Euclidean space, SCG '02/DCG '03, they were used to show that Rao's theorem is tight: series-parallel, and hence planar, graphs can require \Omega(\sqrt{\log n}) distortion to embed into Euclidean space.

- Wed 3/1: Impossibility of dimensionality reduction in L_1.
- The impossibility result was first shown by Brinkman/Charikar, On the Impossibility of Dimension Reduction in l, FOCS '03.
- This lecture followed the shorter proof in Lee/Naor, Embedding the diamond graph in Lp and dimension reduction in L1, Geometric and Functional Analysis, 2004. See here for a proof of the uniform convexity inequality used in the paper. See this Web page by James Lee for the geometric intuition behind the inequality.

- Mon 3/6: Doubling metrics and nearest neighbor search. References:
- Gupta/Krauthgamer/Lee, Bounded geometries, fractals, and low-distortion embeddings, FOCS 2003.
- Krauthgamer/Lee, Navigating nets: Simple algorithms for proximity search, SODA 2004.

- Krauthgamer/Lee, The black-box complexity of nearest neighbor search, ICALP 2004.
- Har-Peled/Mendel, Fast Construction of Nets in Low Dimensional Metrics, and Their Applications, SCG 2005.
- Cole/Gottlieb, Searching Dynamic Point Sets in Spaces with Bounded Doubling Dimension, to appear in STOC 2006.

- Talwar, Bypassing the embedding: algorithms for low dimensional metrics, STOC 2004.

- Wed 3/8: The ARV algorithm for uniform sparsest cut.
References:
- Arora/Rao/Vazirani, Expander Flows, Geometric Embeddings, and Graph Partitionings, STOC 2004.
- Section 4 of Lee, Distance scales, embeddings, and metrics of negative type, SODA 2005.

- Mon 3/13: More on the ARV algorithm for uniform sparsest cut.
- Wed 3/15: Finish the ARV algorithm for uniform sparsest cut.

**Bonus lectures (Spring 2006):**

- Tue 4/25: Introduction to the bandwidth problem; construction of
volume-respecting embeddings. Our main references are:
- Feige, Approximating the Bandwidth via Volume Respecting Embeddings, STOC 1998/JCSS 2000.
- Lectures 17-20 from the Gupta/Ravi course.

- Dunagan/Vempala, On Euclidean embeddings and bandwidth minimization, APPROX 2001 (a bit better approximation ratio);
- Rao, Small distortion and volume preserving embeddings for planar and Euclidean metrics, SCG '99 (a different construction of volume-respecting embeddings, plus improved results for graphs excluding a fixed minor);
- Gupta, Improved Bandwidth Approximation for Trees and Chordal Graphs, SODA 2000/J Algorithms 2001 (improved results for trees);
- Feige/Talwar, Approximating the Bandwidth of Caterpillars, APRROX 2005 (better bounds for caterpillars);
- Unger, The Complexity of the Approximation of the Bandwidth Problem, FOCS 1998 (inapproximability results);
- Vempala, Random Projection: A New Approach to VLSI Layout, FOCS 1998 (application of volume-respecting embeddings to graph partitioning).

- Vempala, The Random Projection Method, AMS, 2004.

- Tue 5/2: Finish construction of volume-respecting embeddings.
Analysis of Feige's bandwidth algorithm. (See references from
last week.)
- Tue 5/9: Euclidean embeddings of negative type metrics
and the (general) sparsest cut problem.
We will focus on:
- Chawla/Gupta/Racke, Embeddings of Negative-type Metrics and An Improved Approximation to Generalized Sparsest Cut, SODA 2005, which gives an O(log^{3/4} n)-distortion embedding of l_2^2 metrics into l_2.

- Arora/Lee/Naor, Euclidean distortion and the Sparsest Cut, STOC 2005.
- A high-level overview of the ALN embedding is given in these scribe notes from a course of Sanjeev Arora. (See below for measured descent references.)

- Tue 5/16: Euclidean embeddings of negative type metrics
and the (general) sparsest cut problem (con'd); see references
above.
- Tue 5/30: Aspects of measured descent; a third proof of
Bourgain's theorem. Main reference:
- Scribe notes from Sanjeev Arora's course.

- Krauthgamer/Lee/Mendel/Naor, Measured descent: A new embedding method for finite metrics, FOCS 2004

- Lee, Distance scales, embeddings, and metrics of negative type, SODA 2005.