Embedding the diamond graph inLpand dimension reduction inL1 |
| |
Authors: | James R. Lee and Assaf Naor |
| |
Affiliation: | (1) Computer Science Division, University of California at Berkeley, 94720-3840 Berkeley, CA, USA;(2) Microsoft Research, One Microsoft Way, Redmont, WA 98103-6399, USA |
| |
Abstract: | We show that any embedding of the level k diamond graph ofNewman and Rabinovich [NR] into Lp, 1 < p 2, requires distortion atleast . An immediate corollary is that there exist arbitrarilylarge n-point sets such that any D-embedding of X into requires. This gives a simple proof of a recent result of Brinkmanand Charikar [BrC] which settles the long standing question of whetherthere is an L1 analogue of the Johnson-Lindenstrauss dimension reductionlemma [JL]. |
| |
Keywords: | ((no given)) |
本文献已被 SpringerLink 等数据库收录! |
|