Rafail Ostrovsky - Publications

Low distortion embeddings for edit distance.

Rafail Ostrovsky, Yuval Rabani


We show that $\{0,1\}^d$ endowed with edit distance embeds into $\ell_1$ with distortion $2^{O\left(\sqrt{\log d\log\log d}\right)}$. We further show efficient implementations of the embedding that yield solutions to various computational problems involving edit distance. These include sketching, communication complexity, nearest neighbor search. For all these problems, we improve upon previous bounds.

comment: J. ACM 54(5): (2007). Preliminary version in Proceedings of (STOC-2005).

Fetch PostScript file of the paper     Fetch PDF file of the paper

Back to the Rafail Ostrovsky publication list or to the Rafail Ostrovsky main page.