This is an announcement for the paper "Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits" by Shachar Lovett and Sasha Sodin.

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.

Archive classification: Functional Analysis; Metric Geometry; Probability

Remarks: 16 pages

The source file(s), derand.tex: 32081 bytes, is(are) stored in gzipped form as 0701102.gz with size 11kb. The corresponding postcript file has gzipped size 109kb.

Submitted from: sodinale@post.tau.ac.il

The paper may be downloaded from the archive by web browser from URL

http://front.math.ucdavis.edu/math.FA/0701102

or

http://arXiv.org/abs/math.FA/0701102

or by email in unzipped form by transmitting an empty message with subject line

uget 0701102

or in gzipped form by using subject line

get 0701102

to: math@arXiv.org.