Lecture Topics and Notes
Lecture 1 (September 25, 2018): Metric Spaces, Embeddings, and Distortion
Jiri Matousek, Lecture Notes on Metric Embeddings, Sections 1.1-1.4 (we covered until page 12, the definition of line and cut metrics)
Lecture 2 (September 27, 2018): Embeddings into ell_infinity
Jiri Matousek, Lecture Notes on Metric Embeddings, The Frechet embedding (page 17) and Section 4.1
Lecture 3 (October 2, 2018): Bourgain’s Theorem and the Sparsest Cut Problem
Jiri Matousek, Lecture Notes on Metric Embeddings, Sections 4.2-4.3
Lecture 4 (October 4, 2018): Uniform Sparsest Cut via Bourgain’s Embedding
Jiri Matousek, Lecture Notes on Metric Embeddings, Section 4.3 and Section 3.3
Lecture 5 (October 9, 2018): Lower Bounds on the Dimensions of Low Distortion Embeddings into Normed Spaces
Jiri Matousek, Lecture Notes on Metric Embeddings, Section 3.3 and Section 3.5
Lecture 6 (October 11, 2018): A Lower Bound on the Distortion of Embeddings into ell_2
Jiri Matousek, Lecture Notes on Metric Embeddings, Section 3.5
Oded Regev, Entropy-based Bounds on Dimension Reduction in L_1, Israel Journal of Mathematics, 2013
Lecture 7 (October 16, 2018): Lower Bounds on Dimension Reduction in ell_1
Oded Regev, Entropy-based Bounds on Dimension Reduction in L_1, Israel Journal of Mathematics, 2013
Lecture 8 (October 18, 2018): Probabilistic Embedding into Tree Metrics: Introduction and Applications
David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, Sections 8.5-8.6
Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar, Algorithms Column: Approximating Metrics by Tree Metrics, SIGACT News 2004
Lecture 9 (October 23, 2018): Probabilistic Embedding into Tree Metrics
James R. Lee, Approximation by Ultrametrics
Lecture 10 (October 25, 2018): Metric Ramsey Phenomena and Approximate Distance Oracles
James R. Lee, Approximation by Ultrametrics
Manor Mendel and Assaf Naor, Ramsey Partitions and Proximity Data Structures, FOCS 2006/Journal of the European Mathematical Society 2007
Lectures 11-13 (October 30, 2018 - November 6, 2018): Solving Problems with Capacities using Probabilistic Embedding into Trees
Harald Räcke, Optimal Hierarchical Decompositions for Congestion Minimization in Networks, STOC 2008
Reid Andersen and Uriel Feige, Interchanging Distance and Capacity in Probabilistic Mappings, arXiv 2009
Lecture 14 (November 8, 2018): Lower Bound on Embedding Edit Distance into ell_1
Jiri Matousek, Lecture Notes on Metric Embeddings, Section 3.9
Lectures 15-16 (November 13, 2018 - November 15, 2018): Approximating Sparsest Cut using Semidefinite Programming
Thomas Rothvoss, Lecture Notes on the ARV Algorithm for Sparsest Cut, arXiv 2016
Lecture 17 (November 27, 2018): Doubling Metrics and Other Notions of Distortion
Lecture 18 (November 29, 2018): Routing using Embedding into Hyperbolic Spaces
Lecture 19 (December 4, 2018): Machine Learned Word Embeddings