A classic functional analytic result by Johnson and Lindenstrauss from 1984 implies that
any Euclidean metric on n points can be represented using only k=(log n)/epsilon2
dimensions with distortion epsilon.  In computer science, this result has been
extensively used in design of algorithms suffering from large dependence of space or time
in the dimensionality of the input (images are typically represented using thousands of
dimensions).

In spite of the algorithmic usefulness of dimension reduction, and aside from various
constant factor speedups and proof simplification results, very little was known about
its complexity.  In my talk I will present the first asymptotic improvement to the naive
implementation as well as various applications and questions.

This is based on joint work with Bernard Chazelle.