Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits
<|reference_start|>Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits: 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. Extending earlier work by Artstein--Avidan and Milman, we prove that such a subspace can be generated using O(N) random bits.<|reference_end|>
@article{lovett2007almost,
    title={Almost Euclidean sections of the N-dimensional cross-polytope using O(N)
  random bits},
    author={Shachar Lovett and Sasha Sodin},
    journal={Commun. Contemp. Math. 10 (2008), no. 4, 477--489.},
    year={2007},
    doi={10.1142/S0219199708002879},
    archivePrefix={arXiv},
    eprint={math/0701102},
    primaryClass={math.FA cs.CC math.MG}
}