## Entropy-based Bounds on Dimension Reduction in L1

Oded Regev

#### Oded's comments

The lower bound proof uses the very hard instances utilized
in prior proofs, but reduces the analysis of any L1-embedding of
small distortion to the analysis of a rather loseless compression scheme
(i.e., one that allows to recover each original bit,
with high probability, based on the compressed value
and all previous original bits). Specifically, lower
bounds on the dimension are obtained via lower bounds
on the compression possible in such compression schemes.

#### The original abstract

We show that there exists an N-point subset of L_1 such that for
every D>1, embedding it into \ell_1^d with distortion D requires
dimension d at least N^{\Omega(1/D^2)}, and that for every \eps>0
there exists an N-point subset of L_1 such that embedding it into
\ell_1^d with distortion 1+\eps requires dimension d at least
N^{1-O(1/\log(1/\eps))}. 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.

Back to
list of Oded's choices.