## Overcoming the L_1 Non-Embeddability Barrier

#### Robert KrauthgamerWeizmann Institute of Science

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.]

Back to Quantitative and Computational Aspects of Metric Geometry