Derandomized dimensionality reduction with applications

The Johnson-Lindenstrauss lemma provides a way to map a number of points in high-dimensional space into a low-dimensional space, with only a small distortion of the distances between the points. The proofs of the lemma are non-constructive: they show that a random mapping induces small distortions with high probability, but they do not construct the actual mapping. In this paper, we provide a procedure that constructs such a mapping deterministically in time almost linear in the number of distances to preserve times the dimension of the original space. We then use that result (together with Nisan's pseudorandom generator) to obtain an efficient derandomization of several approximation algorithms based on semidefinite programming.