Title:  Overcoming the L_1 non-embeddability barrier: Algorithms for product spaces 

Speaker: Alex Andoni, MIT 


Abstract:
A common approach for solving computational problems over a
"difficult" metric space is to embed the hard  metric into L_1, which admits
efficient algorithms and is thus considered an "easy"  metric. Over years,
this approach has proved successful or partially successful for important
spaces such as the edit distance, but it also has inherent limitations: it
is provably impossible to go below certain approximation for some metrics.

We propose a new approach, of embedding the difficult space into
richer host spaces, namely iterated products of standard spaces like
L_1 and L_infinity.  We show that this class is rich since it contains
useful metric spaces with only a constant distortion, and, at the same
time, it is tractable and admits efficient algorithms.

Using this approach, we obtain for example the first nearest neighbor
data structure with O(log log d) approximation for edit distance in
non-repetitive strings (the Ulam metric). This approximation is
exponentially better than the lower bound for embedding into
L_1. Furthermore, we give constant factor approximation algorithms for
two other computational problems.  Along the way, we answer positively
some questions left open in [Ajtai-Jayram-Kumar-Sivakumar,
STOC'02]. One of our algorithms has already found applications for
smoothed edit distance over 0-1 strings [Andoni-Krauthgamer,
ICALP'08].

Joint work with Piotr Indyk (MIT) and Robert Krauthgamer (Weizmann
Inst).