How well do finite metric spaces embed in Euclidean space?

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/loglog n. The lower bound shows in particular that O(√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.