[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Nonembeddability theorems via Fourier analysis

  • Published:
Mathematische Annalen Aims and scope Submit manuscript

Abstract

Various new nonembeddability results (mainly into L 1) are proved via Fourier analysis. In particular, it is shown that the Edit Distance on {0,1}d has L 1 distortion We also give new lower bounds on the L 1 distortion of flat tori, quotients of the discrete hypercube under group actions, and the transportation cost (Earthmover) metric.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Andoni, A., Deza, M., Gupta, A., Indyk, P., Raskhodnikova, S.: Lower bounds for embedding edit distance into normed spaces. In: SODA '03: Proceedings of the fourteenth annual ACM-SIAM Symposium on Discrete Algorithms, pp 523–526. Society for Industrial and Applied Mathematics, 2003

  2. Archer, A., Fakcharoenphol, J., Harrelson, C., Krauthgamer, R., Talwar, K., Tardos, E.: Approximate classification via earthmover metrics. In: SODA '04: Proceedings of the fifteenth annual ACM-SIAM Symposium on Discrete Algorithms, pp 1079–1087. Society for Industrial and Applied Mathematics, 2004

  3. Aumann, Y., Rabani, Y.: An O(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput. 27(1), 291–301 (electronic), (1998)

    Article  MathSciNet  Google Scholar 

  4. Ball, K., Carlen, E.A., Lieb, E.H.: Sharp uniform convexity and smoothness inequalities for trace norms. Invent. Math. 115(3), 463–482 (1994)

    Article  Google Scholar 

  5. Bar-Yossef, Z., Jayram, T.S., Krauthgamer, R., Kumar, R.: Approximating edit distance efficiently. In: 45th Annual IEEE Symposium on Foundations of Computer Science, pp 550–559. IEEE, Oct. 2004

  6. Bartal, Y., Linial, N., Mendel, M., Naor, A.: On metric Ramsey-type phenomena. Ann. Math. 162(2), 643–709 (2005)

    Article  MathSciNet  Google Scholar 

  7. Bates, J., Johnson, W.B., Lindenstrauss, J., Preiss, D., Schechtman, G.: Affine approximation of Lipschitz functions and nonlinear quotients. Geom. Funct. Anal. 9(6), 1092–1127 (1999)

    Article  MathSciNet  Google Scholar 

  8. Batu, T., Ergun, F., Kilian, J., Magen, A., Raskhodnikova, S., Rubinfeld, R., Sami, R.: A sublinear algorithm for weakly approximating edit distance. In: STOC '03: Proceedings of the thirty-fifth annual ACM Symposium on Theory of Computing, pp 316–324. New York, NY, USA, ACM Press, 2003

  9. Beckner, W.: Inequalities in Fourier analysis. Ann. of Math. (2) 102(1), 159–182 (1975)

    Google Scholar 

  10. Benyamini, Y., Lindenstrauss, J.: Geometric nonlinear functional analysis. Vol. 1, volume 48 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2000

  11. Beutelspacher, A., Rosenbaum, U.: Projective geometry: from foundations to applications. Cambridge University Press, Cambridge, 1998

  12. Bonami, A.: Étude des coefficients de Fourier des fonctions de L p(G). Ann. Inst. Fourier (Grenoble), 20(fasc. 2), 335–402 (1971), (1970)

  13. Bourgain, J.: On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math. 52(1–2), 46–52 (1985)

    Google Scholar 

  14. Bourgain, J.: The metrical interpretation of superreflexivity in Banach spaces. Israel J. Math. 56(2), 222–230 (1986)

    MathSciNet  Google Scholar 

  15. Bourgain, J.: On the distributions of the Fourier spectrum of Boolean functions. Israel J. Math. 131, 269–276 (2002)

    MATH  MathSciNet  Google Scholar 

  16. Bourgain, J., Kalai, G.: Influences of variables and threshold intervals under group symmetries. Geom. Funct. Anal. 7(3), 438–461 (1997)

    Article  MathSciNet  Google Scholar 

  17. Bourgain, J., Milman, V., Wolfson, H.: On type of metric spaces. Trans. Amer. Math. Soc. 294(1), 295–317 (1986)

    Article  MathSciNet  Google Scholar 

  18. Bridson, M.R., Haefliger, A.: Metric spaces of non-positive curvature, volume 319 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 1999

  19. Buser, P.: A note on the isoperimetric constant. Ann. Sci. École Norm. Sup. (4) 15(2), 213–230 (1982)

    Google Scholar 

  20. Charikar, M., Krauthgamer, R.: Embedding edit distance submetrics into ℓ1. Manuscript, 2005

  21. Charikar, M.S.: Similarity estimation techniques from rounding algorithms. In: STOC '02: Proceedings of the thiry-fourth annual ACM Symposium on Theory of Computing, pp 380–388. ACM Press, 2002

  22. Cheeger, J.: A lower bound for the smallest eigenvalue of the Laplacian. In: Problems in analysis (Papers dedicated to Salomon Bochner, 1969), pp 195–199. Princeton Univ. Press, Princeton, N. J., 1970

  23. Chekuri, C., Khanna, S., Naor, J., Zosin, L.: Approximation algorithms for the metric labeling problem via a new linear programming formulation. In: SODA '01: Proceedings of the twelfth annual ACM-SIAM Symposium on Discrete Algorithms, pp 109–118. Society for Industrial and Applied Mathematics, 2001

  24. Cormode, G., Muthukrishnan, S.: The string edit distance matching problem with moves. In: SODA '02: Proceedings of the thirteenth annual ACM-SIAM Symposium on Discrete Algorithms, pp 667–676. Society for Industrial and Applied Mathematics, 2002

  25. Deza, M.M., Laurent, M.: Geometry of cuts and metrics, volume 15 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 1997

  26. Enflo, P.: On the nonexistence of uniform homeomorphisms between L p -spaces. Ark. Mat. 8, 103–105 (1969)

    MathSciNet  Google Scholar 

  27. Gromov, M.: Metric structures for Riemannian and non-Riemannian spaces, volume 152 of Progress in Mathematics. Birkhäuser Boston Inc., Boston, MA, 1999. Based on the 1981 French original, With appendices by M. Katz, P. Pansu and S. Semmes, Translated from the French by Sean Michael Bates

  28. Gruber, P.M., Lekkerkerker, C.G.: Geometry of numbers, volume 37 of North-Holland Mathematical Library. North-Holland Publishing Co., Amsterdam, second edition, 1987

  29. Guibas, L.J., Rubner, Y., Tomassi, C.: The earth mover's distance as a metric for image retrieval. Int. J Comput. Vis. 40(2), 99–121 (2000)

    MathSciNet  Google Scholar 

  30. Gusfield, D.: Algorithms on strings, trees, and sequences. Cambridge University Press, Cambridge, 1997. Computer science and computational biology

  31. Indyk, P.: Approximate nearest neighbor under edit distance via product metrics. In: SODA '04: Proceedings of the fifteenth annual ACM-SIAM Symposium on Discrete Algorithms, pp 646–650. Society for Industrial and Applied Mathematics, 2004

  32. Indyk, P., Thaper, N.: Fast image retrieval via embeddings. In: ICCV '03: Proceedings of the 3rd International Workshop on Statistical and Computational Theories of Vision, 2003

  33. Kahn, J., Kalai, G., Linial, N.: The influence of variables on Boolean functions. In: 29th Symposium on Foundations of Computer Science, pp 68–80 (1988)

  34. Kassabov, M.: Symmetric groups and expander graphs. Manuscript, 2005. Available online at http://arxiv.org/abs/math.GR/0505624

  35. Khot, S., Naor, A.: Nonembeddability theorems via Fourier analysis (with an appendix on quantitative estimates in Bourgain's noise sensitivity theorem). Available online at http://arxiv.org/abs/math/0510547

  36. Khot, S., Vishnoi, N.: The unique games conjecture, integrality gap for cut problems, and embeddability of negative type metrics into L 1. In: 46th Annual IEEE Symposium on Foundations of Computer Science, pp 53–62. IEEE, Oct. 2005

  37. Lagarias, J.C., Lenstra, H.W. JR., Schnorr, C.P.: Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice. Combinatorica 10(4), 333–348 (1990)

    Article  MathSciNet  Google Scholar 

  38. Ledoux, M.: The concentration of measure phenomenon, volume 89 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2001

  39. Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Dokl. 10, 707–710 (1965)

    MathSciNet  Google Scholar 

  40. Linial, N.: Finite metric spaces – combinatorics, geometry and algorithms. In: Proceedings of the International Congress of Mathematicians III, pp 573–586, 2002

  41. Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some of its algorithmic applications. Combinatorica 15(2), 215–245 (1995)

    Article  MathSciNet  Google Scholar 

  42. MacWilliams, F.J., Sloane, N.J.A.: The theory of error-correcting codes. I, Vol. 16. North-Holland Publishing Co., Amsterdam, North-Holland Mathematical Library, 1977

  43. Martinet, J.: Perfect lattices in Euclidean spaces, volume 327 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 2003

  44. Matoušek, J.: On embedding expanders into l p spaces. Israel J. Math. 102, 189–197 (1997)

    MathSciNet  MATH  Google Scholar 

  45. Matoušek, J.: Open problems on embeddings of finite metric spaces. Available online at http://kam.mff.cuni.cz/~matousek/metrop.ps.gz, 2002

  46. Mendel, M., Naor, A.: Euclidean quotients of finite metric spaces. Adv. Math. 189(2), 451–494 (2004)

    Article  MathSciNet  Google Scholar 

  47. Mendel, M., Naor, A.: Metric cotype. Manuscript, 2005. Available online at http://arxiv.org/abs/math.FA/0506201

  48. Micciancio, D., Goldwasser, S.: Complexity of lattice problems. The Kluwer International Series in Engineering and Computer Science, 671. Kluwer Academic Publishers, Boston, MA, 2002. A cryptographic perspective

  49. Milman, V.D., Schechtman, G.: Asymptotic theory of finite-dimensional normed spaces, volume 1200 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1986. With an appendix by M. Gromov

  50. Muthukrishnan, S., Sahinalp, S.C.: Approximate nearest neighbors and sequence comparison with block operations. In: STOC 2000: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, pp 416–424, 2000

  51. Naor, A., Peres, Y., Schramm, O., Sheffield, S.: Markov chains in smooth Banach spaces and Gromov hyperbolic metric spaces. Manuscript, 2004. Available online at http://arxiv.org/abs/math.FA/0410422

  52. Naor, A., Rabani, Y., Sinclair, A.: Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs. J. Funct. Anal. 227(2), 273–303 (2005)

    Article  MathSciNet  Google Scholar 

  53. Naor, A., Schechtman, G.: Remarks on non linear type and Pisier's inequality. J. Reine Angew. Math. 552, 213–236 (2002)

    MATH  MathSciNet  Google Scholar 

  54. Nash, J.: C 1 isometric imbeddings. Ann. of Math. (2) 60, 383–396 (1954)

  55. Ostrovsky, R., Rabani, Y.: Low distortion embeddings for edit distance. In: STOC 2005: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp 218–224, 2005

  56. Pisier, G.: Martingales with values in uniformly convex spaces. Israel J. Math. 20(3–4), 326–350 (1975)

    Google Scholar 

  57. Pisier, G.: Probabilistic methods in the geometry of Banach spaces. In: Probability and analysis (Varenna, 1985), volume 1206 of Lecture Notes in Math., pp 167–241. Springer, Berlin, 1986

  58. Rozenman, E., Shalev, A., Wigderson, A.: A new family of Cayley expanders? In: STOC 2004: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp 445–454, 2004

  59. Schechtman, G.: Lévy type inequality for a class of finite metric spaces. In: Martingale theory in harmonic analysis and Banach spaces (Cleveland, Ohio, 1981), volume 939 of Lecture Notes in Math., pp 211–215. Springer, Berlin, 1982

  60. Stein, E.M., Weiss, G.: Introduction to Fourier analysis on Euclidean spaces. Princeton University Press, Princeton, N.J., 1971. Princeton Mathematical Series, No. 32

  61. Villani, C.: Topics in optimal transportation, volume 58 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2003

  62. Zong, C.: From deep holes to free planes. Bull. Amer. Math. Soc. (N.S.) 39(4), 533–555 (electronic), 2002

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Georgia Institute of Technology, USA

    Subhash Khot

  2. Microsoft Research, USA

    Assaf Naor

Authors
  1. Subhash Khot
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Assaf Naor
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Assaf Naor.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Khot, S., Naor, A. Nonembeddability theorems via Fourier analysis. Math. Ann. 334, 821–852 (2006). https://doi.org/10.1007/s00208-005-0745-0

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00208-005-0745-0

Mathematics Subject Classification (2000)

Search

Navigation