Nonembeddability theorems via Fourier analysis
Preprint
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.
Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- Metric Structures for Riemannian and Non-Riemannian Spaces2007
- Perfect Lattices in Euclidean Spaces2003
- Complexity of Lattice Problems2002
- Sharp uniform convexity and smoothness inequalities for trace norms2002
- On embedding expanders into ℓ p spacesIsrael Journal of Mathematics, 1997
- Geometry of Cuts and Metrics1997
- The geometry of graphs and some of its algorithmic applicationsCombinatorica, 1995
- Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal latticeCombinatorica, 1990
- The metrical interpretation of superreflexivity in banach spacesIsrael Journal of Mathematics, 1986
- Martingales with values in uniformly convex spacesIsrael Journal of Mathematics, 1975