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 >= 1, 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].