Planar Earthmover is not in $L_1$

Assaf Naor, Gideon Schechtman

We show that any $L_1$ embedding of the transportation cost (a.k.a. Earthmover) metric on probability measures supported on the grid $\{0,1,...,n{\}}^2\subseteq {\mathbb{R}}^2$ incurs distorti…