Metric Embeddings

Spring Semester 2026

Course description [PDF]

Course calendar

• Lecture 1: Examples of isometric embeddings: Fréchet's embedding, Schoenberg's theorem and snowflakes of Hilbert space [WW75, Chapter I], embedding snowflakes of Lp into Lq [MN04, Remark 5.10], Ball's isometric embedding theorem [Bal90], linear embedding of ℓ2 into Lp .

• Lecture 2: Bourgain's embedding theorem (see [Bou85] or [Mat02, Section 15.7]) and its sharpness for expanders by Linial, London and Rabinovich (see [LLR95] or [Mat02, Section 15.5]).

• Lecture 3: The Johnson-Lindenstrauss flattening lemma (see [JL84] or [Mat02, Section 15.2]) and Matoušek's embedding theorem into low-dimensional ℓ∞ (see [Mat92, Mat96] or [Mat02, Section 15.6]).

• Lecture 4: Planar graphs, Rao's embedding theorem [Rao99] and the Klein-Plotkin-Rao stochastic decomposition for planar graphs [KPR93].

• Lecture 5: Proof of the Klein-Plotkin-Rao theorem and doubling metric spaces.

• Lecture 6: Padded decompositions for doubling spaces [GKL03] and single scale embeddings.

• Lecture 7: The Gupta-Krauthgamer-Lee [GKL03] and Assouad [Ass83] embedding theorems, nonembeddability of cycles into trees [RR98] and padded decompositions with respect to ball growth [FRT04, MN07].

• Lecture 8: The embedding theorem of Fakcharoenphol, Rao and Talwar [FRT04], the result of Charikar, Indyk and Tharper [Cha02, IT03] for embeddings of transportation cost spaces into L1, and ultrametric spaces.

• Lecture 9: The nonlinear Dvoretzky theorem for large distortion [MN07], uniform convexity and smoothness of Lp spaces [Gar07, Section 9.8], martingale type and cotype [Pis75].

• Lecture 10: Nonembeddability of hypercubes into uniformly smooth spaces [Ole96] and of diamond graphs into uniformly convex spaces [LN04].

• Lecture 11: Nonembeddability of trees [Bou86] and hypertori [EMN19] into uniformly convex spaces, Markov type [Bal92] and nonembeddability of high girth graphs [LMN02].

Problems [PDF]

References

[Ass83] P. Assouad, Plongements lipschitziens dans R^n, Bulletin de la Société Mathématique de France, 1983.

[Bal90] K. Ball, Isometric embedding in ℓp  spaces, European Journal of Combinatorics, 1990.

[Bal92] K. Ball, Markov chains, Riesz transforms and Lipschitz maps, Geometric and Functional Analysis, 1992.

[BL00] Y. Benyamini and J. Lindenstrauss, Geometric Nonlinear Functional Analysis, American Mathematical Society, 2000.

[Bou85] J. Bourgain, On Lipschitz embedding of finite metric spaces in Hilbert space, Israel Journal of Mathematics, 1985.

[Bou86] J. Bourgain, The metrical interpretation of super-reflexivity in Banach spaces, Israel Journal of Mathematics, 1986.

[Cha02] M. Charikar, Similarity estimation techniques from rounding algorithms, STOC 2002.

[EMN19] A. Eskenazis, M. Mendel and A. Naor, Nonpositive curvature is not coarsely universal, Inventiones Mathematicae, 2019.

[FRT04] J. Fakcharoenphol, S. Rao and K. Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Journal of Computer and Systems Sciences, 2004.

[Gar07] D. J. H. Garling, Inequalities: A Journey into Linear Analysis, Cambridge University Press, 2007.

[GKL03] A. Gupta, R. Krauthgamer and J. R. Lee, Bounded geometries, fractals, and low-distortion embeddings, FOCS 2003.

[IT03] P. Indyk and N. Thaper, Fast image retrieval via embeddings, 3rd International Workshop on Statistical and Computational Theories of Vision, 2003.

[JL84] W. B. Johnson and J. Lindenstrauss, Extensions of Lipschitz mappings into a Hilbert space, Contemporary Mathematics, 1984.

[KPR93] P. Klein, S. A. Plotkin, S. Rao, Excluded minors, network decomposition, and multicommodity flow, STOC 1993.

[LN04] J. R. Lee and A. Naor, Embedding the diamond graph in Lp  and dimension reduction in L1, Geometric and Functional Analysis, 2004.

[LLR95] N. Linial, E. London and Y. Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica, 1995.

[LMN02] N. Linial, A. Magen and A. Naor, Girth and Euclidean distortion, Geometric and Functional Analysis, 2002.

[Mat92] J. Matoušek, Note on bi-Lipschitz embeddings into normed spaces, Commentationes Mathimaticae Universitatis Carolinae, 1992.

[Mat96] J. Matoušek, On the distortion required for embedding finite metric spaces into normed spaces, Israel Journal of Mathematics, 1996.

[Mat02] J. Matoušek, Lectures on Discrete Geometry, Springer, 2002.

[MN04] M. Mendel and A. Naor, Euclidean quotients of finite metric spaces, Advances in Mathematics, 2004.

[MN07] M. Mendel and A. Naor, Ramsey partitions and proximity data structures, Journal of the European Mathematical Society, 2007.

[Nao12] A. Naor, An Introduction to the Ribe Program, Japanese Journal of Mathematics, 2012.

[Ole96] K. Oleszkiewicz, On a discrete version of the antipodal theorem, Fundamenta Mathematicae, 1996.

[Ost13] M. Ostrovskii, Metric Embeddings, De Gruyter, 2013.

[Pis75] G. Pisier, Martingales with values in uniformly convex spaces, Israel Journal of Mathematics, 1975.

[RR98] Y. Rabinovich and R. Raz, Lower bounds on the distortion of embedding finite metric spaces in graphs, Discrete & Computational Geometry, 1998.

[Rao99] S. Rao, Small distortion and volume respecting embeddings for planar and Euclidean metrics, SCG 1999.

[WW75] J. H. Wells and L. R. Williams, Embeddings and extensions in analysis, Springer-Verlag, 1975.