Israel CS THEORY DAY

Open University of Israel

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