Improved Lower Bounds for Embeddings into $L_1$

We improve upon recent lower bounds on the minimum distortion of embedding certain finite metric spaces into $L_1$. In particular, we show that for every $n\ge1$, there is an $n$-point metric space of negative type that requires a distortion of $\Omega(\log\log n)$ for such an embedding, implying the same lower bound on the integrality gap of a well-known semidefinite programming relaxation for sparsest cut. This result builds upon and improves the recent lower bound of $(\log\log n)^{1/6-o(1)}$ due to Khot and Vishnoi [The unique games conjecture, integrality gap for cut problems and the embeddability of negative type metrics into $l_1$, in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, IEEE, Piscataway, NJ, 2005, pp. 53-62]. We also show that embedding the edit distance metric on $\{0,1\}^n$ into $L_1$ requires a distortion of $\Omega(\log n)$. This result improves a very recent $(\log n)^{1/2-o(1)}$ lower bound by Khot and Naor [Nonembeddability theorems via Fourier analysis, in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, IEEE, Piscataway, NJ, 2005, pp. 101-112].