Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR07-012 | 20th October 2008 00:00

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

RSS-Feed




Revision #1
Authors: Shachar Lovett, Sasha Sodin
Accepted on: 20th October 2008 00:00
Downloads: 2977
Keywords: 


Abstract:

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.


Paper:

TR07-012 | 22nd January 2007 00:00

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





TR07-012
Authors: Shachar Lovett, Sasha Sodin
Publication: 5th February 2007 08:47
Downloads: 3211
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint