Planar Earthmover is not in $L_1$

Abstract

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 distortion $\Omega (\sqrt{\log n})$. We also use Fourier analytic techniques to construct a simple $L_1$ embedding of this space which has distortion $O(\log n)$.