Assaf Naor
Microsoft Research Theory Group

The Impossibility of Dimension Reduction in L1

In 1984 Johnson and Lindenstrauss proved that any n-point subset of Euclidean space can be embedded in log n dimensions such that all pair-wise distances are essentially preserved. This remarkable property of Euclidean space has been extremely useful in several mathematical and algorithmic contexts. The question of whether this is also possible when Euclidean distances are replaced by L1 distances remained open until recently. In this talk we will present a simple counter-example showing that dimensionality reduction in L1 is generally impossible.

Joint work with James R. Lee