This is an announcement for the paper "Embedding the diamond graph in $L_p$ and dimension reduction in $L_1$" by J. R. Lee and A. Naor.

Abstract: 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^{\Omega(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.

Archive classification: Functional Analysis; Combinatorics; Metric Geometry

Remarks: 3 pages. To appear in Geometric and Functional Analysis (GAFA)

The source file(s), diamond-gafa.tex: 8222 bytes, is(are) stored in gzipped form as 0407520.gz with size 3kb. The corresponding postcript file has gzipped size 31kb.

Submitted from: jrl@cs.berkeley.edu

The paper may be downloaded from the archive by web browser from URL

http://front.math.ucdavis.edu/math.FA/0407520

or

http://arXiv.org/abs/math.FA/0407520

or by email in unzipped form by transmitting an empty message with subject line

uget 0407520

or in gzipped form by using subject line

get 0407520

to: math@arXiv.org.