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