Dimension reduction for finite trees in L_1

James R. Lee, Arnaud de Mesmay, Mohammad Moharrami

We show that every n-point tree metric admits a (1+eps)-embedding into a C(eps) log n-dimensional L_1 space, for every eps > 0, where C(eps) = O((1/eps)^4 log(1/eps)). This matches…