Improved lower bounds for embeddings into L1

ABSTRACT

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 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 {O, 1}ⁿ 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].

REFERENCES

• 1: A. Andoni , M. Deza , A. Gupta , P. Indyk , S. Raskhodnikova, Lower bounds for embedding edit distance into normed spaces, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 2: Sanjeev Arora , James R. Lee , Assaf Naor, Euclidean distortion and the sparsest cut, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060673]
• 3: Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.222-231, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007355]
• 4: Yonatan Aumann , Yuval Rabani, An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm, SIAM Journal on Computing, v.27 n.1, p.291-301, Feb. 1998 [doi>10.1137/S0097539794285983]
• 5: Ziv Bar-Yossef , T. S. Jayram , Robert Krauthgamer , Ravi Kumar, Approximating Edit Distance Efficiently, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.550-559, October 17-19, 2004 [doi>10.1109/FOCS.2004.14]
• 6: Tugkan Batu , Funda Ergün , Joe Kilian , Avner Magen , Sofya Raskhodnikova , Ronitt Rubinfeld , Rahul Sami, A sublinear algorithm for weakly approximating edit distance, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780590]
• 7: J. Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math., 52(1-2):46--52, 1985.
• 8: J. Bourgain. On the distributions of the Fourier spectrum of Boolean functions. Israel J. Math., 131:269--276, 2002.
• 9: S. Chawla, A. Gupta, and H. Räcke. Improved approximations to sparsest cut. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 102--111, 2005.
• 10: Shuchi Chawla , Robert Krauthgamer , Ravi Kumar , Yuval Rabani , D. Sivakumar, On the Hardness of Approximating Multicut and Sparsest-Cut, Proceedings of the 20th Annual IEEE Conference on Computational Complexity, p.144-153, June 11-15, 2005 [doi>10.1109/CCC.2005.20]
• 11: M. M. Deza and M. Laurent. Geometry of cuts and metrics. Springer-Verlag, Berlin, 1997.
• 12: E. Friedgut. Boolean functions with low average sensitivity depend on few coordinates. Combinatorica, 18(1):27--35, 1998.
• 13: E. Friedgut and G. Kalai. Every monotone graph property has a sharp threshold. Proc. Amer. Math. Soc., 124(10):2993--3002, 1996.
• 14: J. Kahn, G. Kalai, and N. Linial. The influence of variables on boolean functions. In Proceedings of the 29th IEEE Symposium on Foundations of Computer Science, pages 68--80, 1988.
• 15: Subhash Khot, On the power of unique 2-prover 1-round games, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510017]
• 16: Subhash Khot , Assaf Naor, Nonembeddability theorems via Fourier analysis, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.101-112, October 23-25, 2005 [doi>10.1109/SFCS.2005.54]
• 17: Subhash A. Khot , Nisheeth K. Vishnoi, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into \ell 1, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.53-62, October 23-25, 2005 [doi>10.1109/SFCS.2005.74]
• 18: Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
• 19: V. I. Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Dokl., 10:707--710, 1965.
• 20: N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215--245, 1995.
• 21: Elchanan Mossel , Ryan O'Donnell , Krzysztof Oleszkiewicz, Noise stability of functions with low in.uences invariance and optimality, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.21-30, October 23-25, 2005 [doi>10.1109/SFCS.2005.53]
• 22: S. B. Needleman and C. D. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48(3):443--453, 1970.
• 23: Rafail Ostrovsky , Yuval Rabani, Low distortion embeddings for edit distance, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060623]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity measures
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory