Subhash Khot, Assaf Naor
Published 2005-10-26Version 1
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.
Comments: With an appendix on quantitative estimates in Bourgain's noise sensitivity theorem. To appear in Mathematiche Annalen. An extended abstract appeared in FOCS 2005
Topological Poincaré type inequalities and lower bounds on the infimum of the spectrum for graphs
Functional Equations and Fourier Analysis
Lower bounds for norms of products of polynomials on $L_p$ spaces
![QR code for arXiv:math/0510547 [math.FA]](http://oss.arxitics.com/images/favicon.svg)