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(\sqrt {\log n} \cdot \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(\sqrt {\log k}\cdot \log \log k) .