Computer Science/Discrete Mathematics Seminar II

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)/epsilon^2 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 typically require 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. Based on joint work with Bernard Chazelle.