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

CREATORChris Gartland 1, Mikhail Ostrovskii
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE99 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-14852

Browse the full library · About the Tower of Babel