Improved lower bounds for embeddings into L₁

Abstract

We simplify and improve upon recent lower bounds on the minimum distortion of embedding certain finite metric spaces into LI. In particular, we show that for infinitely many values of n there are n-point metric spaces of negative type that require a distortion of Ω(log log n) for such an embedding, implying the same lower bound on the integrality gap of a well-known SDP 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 [STOC 2005]. We also show that embedding the edit distance on {0, 1}n into L1 requires a distortion of Ω(log n). This result simplifies and improves a very recent lower bound due to Khot and Naor [FOCS 2005].