  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.
