Euclidean distortion and the sparsest cut

We prove that every n n -point metric space of negative type (and, in particular, every n n -point subset of L 1 L_1 ) embeds into a Euclidean space with distortion O ( log ⁡ n ⋅ log ⁡ log ⁡ n ) O(√log n · log log n) , a result which is tight up to the iterated logarithm factor. As a consequence, we obtain the best known polynomial-time approximation algorithm for the Sparsest Cut problem with general demands. If the demand is supported on a subset of size k k , we achieve an approximation ratio of O ( log ⁡ k ⋅ log ⁡ log ⁡ k ) O(√log k· log log k) .