Israel CS THEORY DAY
Open University of
Division of Computer Science
Date: 17.3.08
Speaker: Yuval Rabani
Title: Low Distortion Embeddings for Edit Distance
Abstract:
We show a low distortion embedding into
$\ell_1$ of $\{0,1\}^d$ endowed with edit distance. We
further show efficient implementations of the embedding that yield solutions to
various computational problems involving edit distance.
This is joint work with Rafail Ostrovsky