Since I’ve been interacting a lot with the theory group at MSR Redmond (see the UW-MSR Theory Center), I’ve been asked occasionally to propose problems in the geometry of finite metric spaces that might be amenable to probabilistic tools. Here’s a fundamental problem that’s wide open. Let be the smallest number such that every -point subset of embeds into with distortion at most . Here’s what’s known.
- Talagrand (following work of Bourgain-Lindenstrauss-Milman and Schechtman) proved that for every , every -dimensional subspace of admits a -distortion embedding into with . In particular, this gives
- Brinkman and Charikar showed that for . A significantly simpler proof was later given by Assaf Naor and myself. (With Brinkman and Karagiozova, we have also shown that this bound is tight for the Brinkman-Charikar examples and their generalizations.)
- Recently, Newman and Rabinovich showed that one can take for any . Their paper relies heavily on the beautiful spectral sparsification method of Batson, Spielman, and Srivastava. In fact, it is shown that one can use only weighted cuts (see the paper for details). This also hints at a limitation of their technique, since it is easy to see that the metric on requires cuts for a constant distortion embedding (and obviously only one dimension).
The open problem is to get better bounds. For instance, we only know that
There is evidence that might be the right order of magnitude. In the large distortion regime, when , results of Arora, myself, and Naor show that .