Nonembeddability theorems via Fourier analysis

Subhash Khot, Assaf Naor

Research output: Contribution to journalArticle

53 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)821-852
Number of pages32
JournalMathematische Annalen
Volume334
Issue number4
DOIs
StatePublished - Apr 1 2006
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Nonembeddability theorems via Fourier analysis'. Together they form a unique fingerprint.

  • Cite this