Abstract of a paper by Assaf Naor and Gideon Schechtman
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.
participants (1)
-
Dale Alspach