Rafail Ostrovsky - Publications


Low distortion embeddings for edit distance.

Rafail Ostrovsky, Yuval Rabani

Abstract:

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.