Anton Malyshev (Weizmann Institute)

Tuesday, June 9, 2015, 10:50 – 12:00, Math -101

Abstract:

Consider a random finite metric space X given by sampling n points in the unit interval uniformly, and a deterministic finite metric space U given by placing n points in the unit interval at uniform distance. With high probability, X will contain some pairs of points at distance roughly 1/n^2, so any bijection from X to U must distort distances by a factor of roughly n. However, with high probability, two of these random spaces, X_1 and X_2, have a bijection which distorts distances by a factor of only about n^(2/3). The exponent of 2/3 is optimal.