Haifa University - Dept. of CS Theory Seminar

Speaker : Robert Krauthgamer, Weizmann.

Title: "Overcoming the L_1 Non-Embeddability Barrier"

Date: Thursday, Dec. 27.

Place: Haifa U. Education Building, room 566.

Time: 12:15 - 13:30

Abstract:

Embeddings provide a general approach to solving problems over
``hard'' metric spaces, by mapping them into an ``easy'' host space.
One of the most convenient host spaces discovered so far is the L_1
space: it is a relatively rich and yet algorithmically tractable.
However, this approach has inherent limitations since some important
metrics do not admit low-distortion embeddings into L_1.

I will show how to overcome this limitation for one such ``hard''
metric, namely the Ulam metric (a variant of the edit distance, where
strings consist of distinct symbols, i.e., permutations).
Specifically, we obtain constant distortion by mapping the Ulam metric
into an alternative, richer, host space, which is an iterated product
of simple spaces like L_1.  As a result, we are able to obtain new
algorithms with a significantly improved approximation.

Joint work with Alex Andoni and Piotr Indyk.