Nonembeddability theorems via Fourier analysis

Subhash Khot; Assaf Naor

doi:10.1007/s00208-005-0745-0

Nonembeddability theorems via Fourier analysis

Subhash Khot, Assaf Naor

Research output: Contribution to journal › Article › peer-review

74 Scopus citations

Abstract

Various new nonembeddability results (mainly into L ₁) are proved via Fourier analysis. In particular, it is shown that the Edit Distance on {0,1} ^d has L ₁ distortion (log d)^1/2-0(1). We also give new lower bounds on the L ₁ distortion of flat tori, quotients of the discrete hypercube under group actions, and the transportation cost (Earthmover) metric.

Original language	English (US)
Pages (from-to)	821-852
Number of pages	32
Journal	Mathematische Annalen
Volume	334
Issue number	4
DOIs	https://doi.org/10.1007/s00208-005-0745-0
State	Published - Apr 2006
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Mathematics

Access to Document

10.1007/s00208-005-0745-0

Cite this

@article{f940edfba1b14ccdb3be7f88a8b0c970,

title = "Nonembeddability theorems via Fourier analysis",

abstract = "Various new nonembeddability results (mainly into L 1) are proved via Fourier analysis. In particular, it is shown that the Edit Distance on {0,1} d has L 1 distortion (log d)1/2-0(1). We also give new lower bounds on the L 1 distortion of flat tori, quotients of the discrete hypercube under group actions, and the transportation cost (Earthmover) metric.",

author = "Subhash Khot and Assaf Naor",

year = "2006",

month = apr,

doi = "10.1007/s00208-005-0745-0",

language = "English (US)",

volume = "334",

pages = "821--852",

journal = "Mathematische Annalen",

issn = "0025-5831",

publisher = "Springer New York",

number = "4",

}

TY - JOUR

T1 - Nonembeddability theorems via Fourier analysis

AU - Khot, Subhash

AU - Naor, Assaf

PY - 2006/4

Y1 - 2006/4

N2 - Various new nonembeddability results (mainly into L 1) are proved via Fourier analysis. In particular, it is shown that the Edit Distance on {0,1} d has L 1 distortion (log d)1/2-0(1). We also give new lower bounds on the L 1 distortion of flat tori, quotients of the discrete hypercube under group actions, and the transportation cost (Earthmover) metric.

AB - Various new nonembeddability results (mainly into L 1) are proved via Fourier analysis. In particular, it is shown that the Edit Distance on {0,1} d has L 1 distortion (log d)1/2-0(1). We also give new lower bounds on the L 1 distortion of flat tori, quotients of the discrete hypercube under group actions, and the transportation cost (Earthmover) metric.

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

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

U2 - 10.1007/s00208-005-0745-0

DO - 10.1007/s00208-005-0745-0

M3 - Article

AN - SCOPUS:33644977894

SN - 0025-5831

VL - 334

SP - 821

EP - 852

JO - Mathematische Annalen

JF - Mathematische Annalen

IS - 4

ER -

Nonembeddability theorems via Fourier analysis

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this