Lower Estimates for L 1 L_{1} -Distortion of Transportation Cost Spaces
Chris Gartland 1, Mikhail Ostrovskii · 2026
Read Lower Estimates for L 1 L_{1} -Distortion of Transportation Cost Spaces by Chris Gartland 1, Mikhail Ostrovskii (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-14852.txt.
Description
Chris Gartland and Mikhail Ostrovskii study lower estimates for L1 distortion of transportation cost spaces, the earth mover's distance between distributions on a finite metric space. Low-distortion embeddings of earth mover's distance into L1, pioneered by Charikar and by Indyk and Thaper, underpin algorithms in computer science and vision, with an O(log n) upper bound long in question.
Grid graphs, especially planar grids, are a fundamental test case, and the authors press the lower-bound side of that question. Their estimates mark how far embeddings can be squeezed before distortion must grow. Optimal transport geometry gains a sharper sense of its embedding limits.
Catalog record
| CREATOR | Chris Gartland 1, Mikhail Ostrovskii |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 99 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-14852