loading...
Planar Earthmover is not in L_1
Berkeley, California October 21-October 24
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.6047th Annual IEEE Symposium on Foundat ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Assaf Naor, Gideon Schechtman, "Planar Earthmover is not in L_1," Foundations of Computer Science, Annual IEEE Symposium on, pp. 655-666, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 2006.
 
 
BibTex
x
 
@article{ 10.1109/FOCS.2006.60,
author = {Assaf Naor and Gideon Schechtman},
title = {Planar Earthmover is not in L_1},
journal ={Foundations of Computer Science, Annual IEEE Symposium on},
volume = {0},
year = {2006},
issn = {0272-5428},
pages = {655-666},
doi = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.60},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, Annual IEEE Symposium on
TI - Planar Earthmover is not in L_1
SN - 0272-5428
SP655
EP666
A1 - Assaf Naor,
A1 - Gideon Schechtman,
PY - 2006
KW - null
VL - 0
JA - Foundations of Computer Science, Annual IEEE Symposium on
ER -
 
Assaf Naor, Microsoft Research
Gideon Schechtman, Weizmann Institute, Israel
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 \mathbb{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).
Citation:
Assaf Naor, Gideon Schechtman, "Planar Earthmover is not in L_1," focs, pp.655-666, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.