skip to main content
10.5555/1109557.1109669acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
Article

Improved lower bounds for embeddings into L1

Published: 22 January 2006 Publication History

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}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].

References

[1]
A. Andoni, M. Deza, A. Gupta, P. Indyk, and S. Raskhodnikova. Lower bounds for embedding edit distance into normed spaces. In Proceedings of the 14th annual ACM-SIAM Symposium on Discrete Algorithms, pages 523--526, 2003.]]
[2]
S. Arora, J. R. Lee, and A. Naor. Euclidean distortion and the sparsest cut. In Proceedings of the 97th Annual ACM Symposium on Theory of Computing, 2005.]]
[3]
S. Arora, S. Rao, and U. Vazirani. Expander flows, geometric embeddings, and graph partitionings. In 36th Annual Symposium on the Theory of Computing, pages 222--231, May 2004.]]
[4]
Y. Aumann and Y. Rabani. An O(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput., 27(1):291--301, 1998.]]
[5]
Z. Bar-Yossef, T. S. Jayram, R. Krauthgamer, and R. Kumar. Approximating edit distance efficiently. In 45th IEEE Symposium on Foundations of Computer Science, pages 550--559. IEEE Computer Soc., 2004.]]
[6]
T. Batu, F. Ergün, J. Kilian, A. Magen, S. Raskhodnikova, R. Rubinfeld, and R. Sami. A sublinear algorithm for weakly approximating edit distance. In 35th Annual ACM Symposium on Theory of Computing, pages 316--324, 2003.]]
[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]
S. Chawla, R. Krauthgamer, R. Kumar, Y. Rabani, and D. Sivakumar. On the hardness of approximating multicut and sparsest-cut. In Proceedings of the 20th Annual IEEE Conference on Computational Complexity, pages 144--153, June 2005.]]
[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]
S. Khot. On the power of unique 2-prover 1-round games. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pages 767--775, 2002.]]
[16]
S. Khot and A. Naor. Nonembeddability theorems via Fourier Analysis. In 46th IEEE Symposium on Foundations of Computer Science, 2005. To appear.]]
[17]
S. Khot and N. K. Vishnoi. The unique games conjecture, integrality gap for cut problems and the embeddability of negative type metrics into l1. In 46th IEEE Symposium on Foundations of Computer Science, 2005. To appear.]]
[18]
T. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46(6):787--832, 1999.]]
[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]
E. Mossel, R. O'Donnell, and K. Oleszkiewicz. Noise stability of functions with low influences: Invariance and optimality. In Proceedings of the 46th IEEE Symposium on Foundations of Computer Science, 2005. To appear.]]
[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]
R. Ostrovsky and Y. Rabani. Low distortion embeddings for edit distance. In Proceedings of the 37th Annual A CM Symposium on Theory of Computing, pages 218--226, 2005.]]

Cited By

View all
  • (2016)Streaming algorithms for embedding and computing edit distance in the low distance regimeProceedings of the forty-eighth annual ACM symposium on Theory of Computing10.1145/2897518.2897577(712-725)Online publication date: 19-Jun-2016
  • (2016)Real-Valued Embeddings and Sketches for Fast Distance and Similarity EstimationCybernetics and Systems Analysis10.1007/s10559-016-9899-x52:6(967-988)Online publication date: 1-Nov-2016
  • (2014)Hierarchical graph partitioningProceedings of the 26th ACM symposium on Parallelism in algorithms and architectures10.1145/2612669.2612699(51-60)Online publication date: 23-Jun-2014
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm
January 2006
1261 pages
ISBN:0898716055

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 22 January 2006

Check for updates

Qualifiers

  • Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2016)Streaming algorithms for embedding and computing edit distance in the low distance regimeProceedings of the forty-eighth annual ACM symposium on Theory of Computing10.1145/2897518.2897577(712-725)Online publication date: 19-Jun-2016
  • (2016)Real-Valued Embeddings and Sketches for Fast Distance and Similarity EstimationCybernetics and Systems Analysis10.1007/s10559-016-9899-x52:6(967-988)Online publication date: 1-Nov-2016
  • (2014)Hierarchical graph partitioningProceedings of the 26th ACM symposium on Parallelism in algorithms and architectures10.1145/2612669.2612699(51-60)Online publication date: 23-Jun-2014
  • (2013)Shift finding in sub-linear timeProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627850(457-465)Online publication date: 6-Jan-2013
  • (2013)Homomorphic fingerprints under misalignmentsProceedings of the forty-fifth annual ACM symposium on Theory of Computing10.1145/2488608.2488726(931-940)Online publication date: 1-Jun-2013
  • (2012)An accurate estimation of the Levenshtein distance using metric trees and Manhattan distanceProceedings of the 6th International Workshop on Software Clones10.5555/2664398.2664399(1-7)Online publication date: 4-Jun-2012
  • (2011)Near-optimal distortion bounds for embedding doubling spaces into L1Proceedings of the forty-third annual ACM symposium on Theory of computing10.1145/1993636.1993737(765-772)Online publication date: 6-Jun-2011
  • (2010)Polylogarithmic approximation for edit distance and the asymmetric query complexityProperty testing10.5555/1986603.1986622(244-252)Online publication date: 1-Jan-2010
  • (2010)Polylogarithmic approximation for edit distance and the asymmetric query complexityProperty testing10.5555/1980617.1980636(244-252)Online publication date: 1-Jan-2010
  • (2010)Approximate Lasserre integrality gap for unique gamesProceedings of the 13th international conference on Approximation, and 14 the International conference on Randomization, and combinatorial optimization: algorithms and techniques10.5555/1886521.1886545(298-311)Online publication date: 1-Sep-2010
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media