Almost-Euclidean subspaces of ${\ell }_1^N$ via tensor products: a simple approach to randomness reduction

Piotr Indyk, Stanislaw Szarek

It has been known since 1970's that the N-dimensional ${\ell }_1$-space contains nearly Euclidean subspaces whose dimension is $\Omega (N)$. However, proofs of existence of such subspaces w…