We show a computationally efficient low distortion embedding of the
binary cube endowed with edit distance into $\ell_1$. This yields
solutions to various computational problems involving edit distance.
They include sketching, communication complexity, and nearest neighbor
search. For all these problems, we improve upon previous bounds.

This is joint work with Rafail Ostrovsky of UCLA