Embedding the diamond graph in Lp and dimension reduction in L1

James R. Lee, Assaf Naor

Research output: Contribution to journalArticlepeer-review

80 Scopus citations

Abstract

We show that any embedding of the level k diamond graph of Newman and Rabinovich [NR] into Lp, 1 < p ≤ 2, requires distortion at least √k(p - 1) + 1. An immediate corollary is that there exist arbitrarily large n-point sets X ⊆ L1 such that any D-embedding of X into ℓ1d requires d ≥ n Ω(1/D2). 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 L1 analogue of the Johnson-Lindenstrauss dimension reduction lemma [JL].

Original languageEnglish (US)
Pages (from-to)745-747
Number of pages3
JournalGeometric and Functional Analysis
Volume14
Issue number4
DOIs
StatePublished - 2004
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Analysis
  • Geometry and Topology

Fingerprint

Dive into the research topics of 'Embedding the diamond graph in Lp and dimension reduction in L1'. Together they form a unique fingerprint.

Cite this