Nonembeddability theorems via Fourier analysis

Subhash Khot, Assaf Naor

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

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-o(1) We also give new lower bounds on the L 1 distortion of quotients of the discrete hypercube under group actions, and the transportation cost (Earthmover) metric.

Original languageEnglish (US)
Title of host publicationProceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005
Pages101-110
Number of pages10
DOIs
StatePublished - 2005
Event46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005 - Pittsburgh, PA, United States
Duration: Oct 23 2005Oct 25 2005

Publication series

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

Other

Other46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005
CountryUnited States
CityPittsburgh, PA
Period10/23/0510/25/05

ASJC Scopus subject areas

  • Engineering(all)

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

  • Cite this

    Khot, S., & Naor, A. (2005). Nonembeddability theorems via Fourier analysis. In Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005 (pp. 101-110). [1530705] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2005). https://doi.org/10.1109/SFCS.2005.54