Improved lower bounds for embeddings into L1
Robert Krauthgamer, Yuval Rabani · 2006
We simplify and improve upon recent lower bounds on the minimum distortion of embedding certain finite metric spaces into L1. In particular, we show that for every n ≥ 1, there is an n-point metric space of negative type that requires a distortion of Ω(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 [Proc. of 46th FOCS, 2005]. We also show that embedding the edit distance metric on {0, 1} n into L1 requires a distortion of Ω(log n). This result simplifies and improves a very recent (log n) 1/2−o(1) lower bound by Khot and Naor [Proc. of 46th FOCS, 2005]. 1