Embedding the diamond graph in $L_p$ and dimension reduction in $L_1$
| dc.creator | Lee, J. R. | |
| dc.creator | Naor, A. | |
| dc.date | 2004-07-30 | |
| dc.date.accessioned | 2026-07-07T05:10:51Z | |
| dc.date.available | 2026-07-07T05:10:51Z | |
| dc.description | We show that any embedding of the level-k diamond graph of Newman and Rabinovich into $L_p$, $1 < p \le 2$, requires distortion at least $\sqrt{k(p-1) + 1}$. An immediate consequence is that there exist arbitrarily large n-point sets $X \subseteq L_1$ such that any D-embedding of X into $\ell_1^d$ requires $d \geq n^{Ω(1/D^2)}$. This gives a simple proof of the recent result of Brinkman and Charikar which settles the long standing question of whether there is an $L_1$ analogue of the Johnson-Lindenstrauss dimension reduction lemma. | |
| dc.description | 3 pages. To appear in Geometric and Functional Analysis (GAFA) | |
| dc.identifier | https://arxiv.org/abs/math/0407520 | |
| dc.identifier | http://arxiv.org/abs/math/0407520 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/72058 | |
| dc.subject | Functional Analysis | |
| dc.subject | Combinatorics | |
| dc.subject | Metric Geometry | |
| dc.title | Embedding the diamond graph in $L_p$ and dimension reduction in $L_1$ | |
| dc.type | text |