Nonembeddability theorems via Fourier analysis
arXiv:math/0510547
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.
With an appendix on quantitative estimates in Bourgain's noise sensitivity theorem. To appear in Mathematiche Annalen. An extended abstract appeared in FOCS 2005