Seminario Interdipartimentale di Algoritmica  

Monday, November 21, 2005, 12:00 noon
Dimension-Reductions in The Hamming Cube and its Applications
Rafail Ostrovsky, UCLA

DI - Department of Computer Science
Seminar Room, third floor

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 show how to use these transformations to solve several proximity problems in the cube as well as in geometric settings. In particular, we survey the problem of preprocessing a dataset of $n$ points so as to allow quick search for an approximate match to a query point and also discuss approximation algorithms for some NP-hard clustering problems.