{
  "id": "math/0510547",
  "version": "v1",
  "published": "2005-10-26T06:34:20.000Z",
  "updated": "2005-10-26T06:34:20.000Z",
  "title": "Nonembeddability theorems via Fourier analysis",
  "authors": [
    "Subhash Khot",
    "Assaf Naor"
  ],
  "comment": "With an appendix on quantitative estimates in Bourgain's noise sensitivity theorem. To appear in Mathematiche Annalen. An extended abstract appeared in FOCS 2005",
  "categories": [
    "math.FA",
    "math.MG"
  ],
  "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 $(\\log d)^{\\frac12-o(1)}$. 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2005-10-26T06:34:20.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "46B20",
      "68U05"
    ],
    "keywords": [
      "fourier analysis",
      "nonembeddability theorems",
      "edit distance",
      "transportation cost",
      "lower bounds"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2005math.....10547K"
    }
  }
}