{
  "id": "0910.0277",
  "version": "v3",
  "published": "2009-10-01T21:45:27.000Z",
  "updated": "2011-04-21T08:18:03.000Z",
  "title": "On the optimality of gluing over scales",
  "authors": [
    "Alexander Jaffe",
    "James R. Lee",
    "Mohammad Moharrami"
  ],
  "comment": "minor revisions",
  "categories": [
    "math.MG"
  ],
  "abstract": "We show that for every $\\alpha > 0$, there exist $n$-point metric spaces (X,d) where every \"scale\" admits a Euclidean embedding with distortion at most $\\alpha$, but the whole space requires distortion at least $\\Omega(\\sqrt{\\alpha \\log n})$. This shows that the scale-gluing lemma [Lee, SODA 2005] is tight, and disproves a conjecture stated there. This matching upper bound was known to be tight at both endpoints, i.e. when $\\alpha = \\Theta(1)$ and $\\alpha = \\Theta(\\log n)$, but nowhere in between. More specifically, we exhibit $n$-point spaces with doubling constant $\\lambda$ requiring Euclidean distortion $\\Omega(\\sqrt{\\log \\lambda \\log n})$, which also shows that the technique of \"measured descent\" [Krauthgamer, et. al., Geometric and Functional Analysis] is optimal. We extend this to obtain a similar tight result for $L_p$ spaces with $p > 1$.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2011-04-21T08:18:03.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "optimality",
      "point metric spaces",
      "similar tight result",
      "point spaces",
      "requiring euclidean distortion"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}