Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits

Shachar Lovett, Sasha Sodin

It is well known that R^N has subspaces of dimension proportional to N on which the \ell_1 norm is equivalent to the \ell_2 norm; however, no explicit constructions are known. Exte…