Planar Earthmover is not in $L_1$
<|reference_start|>Planar Earthmover is not in $L_1$: 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 \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)$.<|reference_end|>
@article{naor2005planar,
    title={Planar Earthmover is not in $L_1$},
    author={Assaf Naor and Gideon Schechtman},
    journal={arXiv preprint arXiv:cs/0509074},
    year={2005},
    archivePrefix={arXiv},
    eprint={cs/0509074},
    primaryClass={cs.CG math.FA}
}