ALMOST EUCLIDEAN SECTIONS OF THE N-DIMENSIONAL CROSS-POLYTOPE USING O(N) RANDOM BITS

DOI10.1142/S0219199708002879zbMATH Open1161.46010arXivmath/0701102MaRDI QIDQ3526528FDOQ3526528

Authors: Shachar Lovett, Sasha Sodin 

Publication date: 25 September 2008

Published in: Communications in Contemporary Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/math/0701102

Recommendations

• Euclidean Sections of $\ell_1^N$ with Sublinear Randomness and Error-Correction over the Reals
• Random polytopes, convex bodies, and approximation
• Approximation by random polytopes has low complexity
• Randomized complexity lower bound for arrangements and polyhedra
• Approximation of convex bodies by random polytopes
• Approximating multidimensional subset sum and Minkowski decomposition of polygons
• scientific article; zbMATH DE number 4119095
• scientific article; zbMATH DE number 1098734
• scientific article; zbMATH DE number 7525513

zbMATH Keywords

embeddingderandomizationcross-polytope\(k\)-wise independencealmost Euclidean sections

Mathematics Subject Classification ID

Randomized algorithms (68W20) Local theory of Banach spaces (46B07) Geometry and structure of normed linear spaces (46B20) Convexity and finite-dimensional Banach spaces (including special norms, zonoids, etc.) (aspects of convex geometry) (52A21) Probabilistic methods in Banach space theory (46B09)

Cites Work

• The dimension of almost spherical sections of convex bodies
• Expander graphs and their applications
• Entropy numbers of diagonal operators between symmetric Banach spaces
• Derandomized graph products
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A limit theorem for the norm of random matrices
• Sampling convex bodies: a random matrix approach
• Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
• Logarithmic reduction of the level of randomness in some probabilistic geometric constructions

Cited In (5)

• Zonoids and sparsification of quantum measurements
• Euclidean Sections of $\ell_1^N$ with Sublinear Randomness and Error-Correction over the Reals
• Almost-Euclidean subspaces of \(\ell_1^N\) via tensor products: a simple approach to randomness reduction
• Explicit Euclidean embeddings in permutation invariant normed spaces
• A counterexample to a strengthening of a question of V. D. Milman

This page was built for publication: ALMOST EUCLIDEAN SECTIONS OF THE N-DIMENSIONAL CROSS-POLYTOPE USING O(N) RANDOM BITS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3526528)