Planar earthmover is not in L1

Assaf Naor, Gideon Schechtman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We show that any L1 embedding of the transportation cost (a.ka. Earthmover) metric on probability measures supported on the grid {0,1,..., n}2 ⊆ ℝ2 incurs distortion Ω (√log n). We also use Fourier analytic techniques to construct a simple L1 embedding of this space which has distortion O (log n).

Original languageEnglish (US)
Title of host publication47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006
Pages655-664
Number of pages10
DOIs
StatePublished - 2006
Event47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006 - Berkeley, CA, United States
Duration: Oct 21 2006Oct 24 2006

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006
Country/TerritoryUnited States
CityBerkeley, CA
Period10/21/0610/24/06

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint

Dive into the research topics of 'Planar earthmover is not in L<sub>1</sub>'. Together they form a unique fingerprint.

Cite this