Nonembeddability theorems via Fourier analysis

Subhash Khot, Assaf Naor

Research output: Contribution to journalArticlepeer-review

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 2006

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

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

Cite this