Metric structures in L1: dimension, snowflakes, and average distortion

We present some new observations concerning the relation of L1 to dimension, topology, and Euclidean distortion. We show that every n-point subset of L1 embeds into L2 with average distortion O(logn), yielding the first evidence that the conjectured worst-case bound of O(logn) is valid. We also address the issue of dimension reduction in Lp for p∈(1,2). We resolve a question left open by M. Charikar and A. Sahai [Dimension reduction in the ℓ1 norm, in: Proceedings of the 43rd Annual IEEE Conference on Foundations of Computer Science, ACM, 2002, pp. 251-260] concerning the impossibility of dimension reduction with a linear map in the above cases, and we show that a natural variant of the recent example of Brinkman and Charikar [On the impossibility of dimension reduction in ℓ1, in: Proceedings of the 44th Annual IEEE Conference on Foundations of Computer Science, ACM, 2003, pp. 514-523], cannot be used to prove a lower bound for the non-linear case. This is accomplished by exhibiting constant-distortion embeddings of snowflaked planar metrics into Euclidean space.