Abstract
We show that any embedding of the level k diamond graph of Newman and Rabinovich [NR] into L p , 1 < p ≤ 2, requires distortion at least \( \sqrt{k(p-1) + 1} \). An immediate corollary is that there exist arbitrarily large n-point sets \( X \subseteq L_1 \) such that any D-embedding of X into \( \ell^d_1 \) requires \( d \geq n^{\Omega(1/D^2)} \). This gives a simple proof of a recent result of Brinkman and Charikar [BrC] which settles the long standing question of whether there is an L 1 analogue of the Johnson-Lindenstrauss dimension reduction lemma [JL].
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Lee, J., Naor, A. Embedding the diamond graph in L p and dimension reduction in L 1 . Geom. funct. anal. 14, 745–747 (2004). https://doi.org/10.1007/s00039-004-0473-8
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/s00039-004-0473-8