Low distortion embeddings for edit distance

October 12, 2006
Yuval Rabani | Technion - Israel Institute of Technology

We show a computationally efficient low distortion embedding of the binary cube endowed with edit distance into ℓ₁. 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.

Speaker Details

Yuval Rabani received his Ph.D. in Computer Science from Tel Aviv University in 1992, under the supervision of professor Amos Fiat. He spent three years as a postdoc in ICSI, Berkeley (1992-93), MIT (1993-94), and the University of Toronto (1994-95). Since 1995 he has been at the Technion – Israel Institute of Technology, where he is currently an associate professor. He spent 2003-2004 on sabbatical in Cornell University as a Mary Upson distinguished visiting professor. He held short-term visiting positions in Cornell University, UCLA, and California Institute of Technology. His main research interests are theory of computation, especially the theory of algorithms, combinatorial optimization, and algorithmic applications of metric geometry.