Planar earthmover is not in L1

Assaf Naor; Gideon Schechtman

doi:10.1109/FOCS.2006.60

Planar earthmover is not in L₁

Assaf Naor, Gideon Schechtman

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

5 Scopus citations

Abstract

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

Original language	English (US)
Title of host publication	47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006
Pages	655-664
Number of pages	10
DOIs	https://doi.org/10.1109/FOCS.2006.60
State	Published - 2006
Externally published	Yes
Event	47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006 - Berkeley, CA, United States Duration: Oct 21 2006 → Oct 24 2006

Publication series

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

Other

Other	47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006
Country/Territory	United States
City	Berkeley, CA
Period	10/21/06 → 10/24/06

All Science Journal Classification (ASJC) codes

General Engineering

Access to Document

10.1109/FOCS.2006.60

Cite this

@inproceedings{66e32dcd251c42bcbe08411b30e373ce,

title = "Planar earthmover is not in L1",

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).",

author = "Assaf Naor and Gideon Schechtman",

year = "2006",

doi = "10.1109/FOCS.2006.60",

language = "English (US)",

isbn = "0769527205",

series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

pages = "655--664",

booktitle = "47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006",

note = "47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006 ; Conference date: 21-10-2006 Through 24-10-2006",

}

Naor, A & Schechtman, G 2006, Planar earthmover is not in L₁. in 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006., 4031400, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 655-664, 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006, Berkeley, CA, United States, 10/21/06. https://doi.org/10.1109/FOCS.2006.60

TY - GEN

T1 - Planar earthmover is not in L1

AU - Naor, Assaf

AU - Schechtman, Gideon

PY - 2006

Y1 - 2006

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=38749142921&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38749142921&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2006.60

DO - 10.1109/FOCS.2006.60

M3 - Conference contribution

AN - SCOPUS:38749142921

SN - 0769527205

SN - 9780769527208

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 655

EP - 664

BT - 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006

T2 - 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006

Y2 - 21 October 2006 through 24 October 2006

ER -