ECCC-Report TR07-012https://eccc.weizmann.ac.il/report/2007/012Comments and Revisions published for TR07-012en-usMon, 20 Oct 2008 00:00:00 +0200
Revision 1
| Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits |
Shachar Lovett,
Sasha Sodin
https://eccc.weizmann.ac.il/report/2007/012#revision1It 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.
Mon, 20 Oct 2008 00:00:00 +0200https://eccc.weizmann.ac.il/report/2007/012#revision1
Paper TR07-012
| Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits |
Shachar Lovett,
Sasha Sodin
https://eccc.weizmann.ac.il/report/2007/012It 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.
Mon, 05 Feb 2007 08:47:38 +0200https://eccc.weizmann.ac.il/report/2007/012