This is an announcement for the paper "Planar earthmover is not in $L_1$" by Assaf Naor and Gideon Schechtman.

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 \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)$.

Archive classification: Computational Geometry; Functional Analysis

The source file(s), , is(are) stored in gzipped form as with size . The corresponding postcript file has gzipped size .

Submitted from: anaor@microsoft.com

The paper may be downloaded from the archive by web browser from URL

http://front.math.ucdavis.edu/cs.CG/0509074

or

http://arXiv.org/abs/cs.CG/0509074

or by email in unzipped form by transmitting an empty message with subject line

uget 09074

or in gzipped form by using subject line

get 09074

to: math@arXiv.org.