How well do finite metric spaces embed in Euclidean space?. Leo Torres.

Bourgain proves that every metric space with $n$ points embeds in Euclidean space with distortion $O(\log n)$, and constructs, from random graphs, metric spaces for which every embedding has distortion at least a constant multiple of $\log n/\log\log n$. The lower bound shows in particular that $O(\sqrt{\log n})$ is not achievable, and answers negatively a question of Johnson and Lindenstrauss (1984) about embeddings into normed spaces of dimension $\log n$. The embedding sends each point to its distances from random sets of points of every size up to $n$, and the analysis rests on a single estimate of how often such a set separates two given points. The theorem became a cornerstone of the theory of low-distortion embeddings of finite metric spaces. A decade later, Linial, London and Rabinovich (1995) made the construction algorithmic and proved that expander graphs require distortion of order $\log n$, so that Bourgain's bound is best possible; with the independent work of Aumann and Rabani (1998), this made the embedding a basic tool of approximation algorithms, beginning with the sparsest cut problem.