Abstract of a paper by Subhash Khot and Assaf Naor
This is an announcement for the paper "Nonembeddability theorems via Fourier analysis" by Subhash Khot and Assaf Naor. 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)^{\frac12-o(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. Archive classification: Functional Analysis; Metric Geometry Mathematics Subject Classification: 46B20; 68U05 Remarks: With an appendix on quantitative estimates in Bourgain's noise The paper may be downloaded from the archive by web browser from URL http://front.math.ucdavis.edu/math.FA/0510547 or http://arXiv.org/abs/math.FA/0510547 or by email in unzipped form by transmitting an empty message with subject line uget 0510547 or in gzipped form by using subject line get 0510547 to: math@arXiv.org.
participants (1)
-
Dale Alspach