Computer Science/Discrete Mathematics Seminar I

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