Advances in Metric Embedding Theory

Ittai Abraham Yair Bartal Ofer Neiman

Abstract A celebrated theorem of Bourgain states that every finite metric space on n pints embeds in Euclidean space with O(log n) distortion. Bourgain's result is best possible when considering the worst case distortion over all pairs of points in the metric space. Yet, is this the case for the average distortion? Our main result is a strengthening of Bourgain's theorem providing an embedding with constant average distortion for arbitrary metric spaces. In fact, our embedding possesses a much stronger property. We define the lq-distortion of a uniformly distributed pair of points. Our embedding achieves the best possible lq-distortion for all 1≤q ≤∞ simultaneously.

[STOC 06 version pdf]