All reports by Author Sasha Sodin:

__
TR07-012
| 22nd January 2007
__

Shachar Lovett, Sasha Sodin#### Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits

Revisions: 1

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.

Extending earlier work by Artstein--Avidan and Milman, we prove that

such a subspace can be generated using $O(N)$ random bits.