[Banach] Abstract of a paper by Assaf Naor and Gideon Schechtman

[Dale Alspach]

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 at 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 at arXiv.org.