# Open problem: Dimension reduction in L_1

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 ${c_D(n)}$ be the smallest number such that every ${n}$-point subset of ${L_1}$ embeds into ${\ell_1^{c_D(n)}}$ with distortion at most ${D}$. Here’s what’s known.

1. Talagrand (following work of Bourgain-Lindenstrauss-Milman and Schechtman) proved that for every ${\varepsilon > 0}$, every ${n}$-dimensional subspace of ${L_1}$ admits a ${(1+\varepsilon)}$-distortion embedding into ${\ell_1^{d}}$ with ${d = O((n \log n)/\varepsilon^2)}$. In particular, this gives

$\displaystyle c_{1+\varepsilon}(n) = O((n \log n)/\varepsilon^2).$

2. Brinkman and Charikar showed that ${c_D(n) \geq \Omega(n^{1/D^2})}$ for ${D \geq 1}$. 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.)
3. Recently, Newman and Rabinovich showed that one can take ${c_{1+\varepsilon}(n) = O(n/\varepsilon^2)}$ for any ${\varepsilon > 0}$. 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 ${O(n/\varepsilon^2)}$ 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 ${\{1,2,\ldots,n\} \subseteq \mathbb R}$ requires ${\Omega(n)}$ 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

$\displaystyle \Omega(n^{1/100}) \leq c_{10}(n) \leq O(n).$

There is evidence that $n^{\Theta(1/D^2)}$ might be the right order of magnitude.  In the large distortion regime, when $D = \Omega(\sqrt{\log n} \log \log n)$, results of Arora, myself, and Naor show that $c_D(n) = O(\log n)$.