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

Dale Alspach alspach at www.math.okstate.edu
Wed Dec 14 16:19:42 CST 2005

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.