ALMOST EUCLIDEAN SECTIONS OF THE N-DIMENSIONAL CROSS-POLYTOPE USING O(N) RANDOM BITS
Shachar Lovett, Sasha Sodin · Communications in Contemporary Mathematics · 2008
It is well known that ℝN has subspaces of dimension proportional to N on which the ℓ1 norm is equivalent to the ℓ2 norm; however, no explicit constructions are known. Extending an earlier work by Artstein-Avidan and Milman, we prove that such a subspace can be generated using O(N) random bits.