## Abstract

We show that for every large enough integer N, there exists an N-point subset of L _{1} such that for every D > 1, embedding it into ℓ _{1} ^{d} with distortion D requires dimension d at least N^{Ω} (1/D^{2}), and that for every e{open} > 0 and large enough integer N, there exists an N-point subset of L _{1} such that embedding it into ℓ _{1} ^{d} with distortion 1 + e{open} requires dimension d at least N^{Ω} (1/D^{2})). These results were previously proven by Brinkman and Charikar [JACM, 2005] and by Andoni, Charikar, Neiman and Nguyen [FOCS 2011]. We provide an alternative and arguably more intuitive proof based on an entropy argument.

Original language | English (US) |
---|---|

Pages (from-to) | 825-832 |

Number of pages | 8 |

Journal | Israel Journal of Mathematics |

Volume | 195 |

Issue number | 2 |

DOIs | |

State | Published - Jun 2013 |

## ASJC Scopus subject areas

- Mathematics(all)

## Fingerprint

Dive into the research topics of 'Entropy-based bounds on dimension reduction in L^{1}'. Together they form a unique fingerprint.