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

Simple item page
dc.creatorLovett, Shachar
dc.creatorSodin, Sasha
dc.date2007-01-03
dc.date2008-10-20
dc.date.accessioned2026-07-07T13:02:14Z
dc.date.available2026-07-07T13:02:14Z
dc.descriptionIt 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.
dc.description16 pages; minor changes in the introduction to make it more accessible to both Math and CS readers
dc.identifierhttps://arxiv.org/abs/math/0701102
dc.identifierhttp://arxiv.org/abs/math/0701102
dc.identifierCommun. Contemp. Math. 10 (2008), no. 4, 477--489.
dc.identifierdoi:10.1142/S0219199708002879
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/226380
dc.subjectFunctional Analysis
dc.subjectComputational Complexity
dc.subjectMetric Geometry
dc.titleAlmost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits
dc.typetext

Files

Collections

arXiv