{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreidny5fhv45xyswqxr2litdj3jl57sz2jqnk7ucz7ipbj7mv2ueram",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mf3zuu2gtt32"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.14852v1",
  "publishedAt": "2026-02-17T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Chris Gartland",
    "Mikhail Ostrovskii"
  ],
  "textContent": "**Authors:** Chris Gartland, Mikhail Ostrovskii\n\nQuantifying the degree of dissimilarity between two probability distributions on a finite metric space is a fundamental task in Computer Science and Computer Vision. A natural dissimilarity measure based on optimal transport is the Earth Mover's Distance (EMD). A key technique for analyzing this metric, pioneered by Charikar (2002) and Indyk and Thaper (2003), involves constructing low-distortion embeddings of EMD(X) into the Lebesgue space $L_1$. It became a key problem to investigate whether the upper bound of $O(\\log n)$ can be improved for important classes of metric spaces known to admit low-distortion embeddings into $L_1$. In the context of Computer Vision, grid graphs, especially planar grids, are among the most fundamental. Indyk posed the related problem of estimating the $L_1$-distortion of the space of uniform distributions on $n$-point subsets of $R^2$. The Progress Report, last updated in August 2011, highlighted two key results: first, the work of Khot and Naor (2006) on Hamming cubes, which showed that the $L_1$-distortion for Hamming cubes meets the described above upper estimate, and second, the result of Naor and Schechtman (2007) for planar grids, which established that the $L_1$-distortion of for a planar $n$ by $n$ grid is $Ω(\\sqrt{\\log n})$. Our first result is the improvement of the lower bound on the $L_1$-distortion for grids to $Ω(\\log n)$, matching the universal upper bound up to multiplicative constants. The key ingredient allowing us to obtain these sharp estimates is a new Sobolev-type inequality for scalar-valued functions on the grid graphs. Our method is also applicable to many recursive families of graphs, such as diamond and Laakso graphs. We obtain the sharp distortion estimates of $\\log n$ in these cases as well.",
  "title": "Lower Estimates for $L_1$-Distortion of Transportation Cost Spaces"
}