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.
Copyright. All Rights Reserved.