Abstract:

The Johnson-Lindenstrauss lemma states that $n$ points
in a high dimensional Hilbert space can be embedded
with small distortion of the distances into an
$O(\log n)$ dimensional space by applying a random
linear transformation. We show that similar properties
hold for certain random linear transformations over
the Hamming cube. We use these transformations to
solve several proximity problems in the cube as well as
in geometric settings. In particular, we discuss the
problem of preprocessing a dataset of $n$ points so
as to allow quick search for an approximate match to a query
point. We also discuss approximation algorithms for
some NP-hard clustering problems and various applications
to internet search engines.

The talk is based on several papers written jointly with
Allan Borodin, Eyal Kushilevitz and Yuval Rabani.