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.
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.