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

DOI10.1142/S0219199708002879MaRDI QIDQ3526528zbMATH OpenFDO

Authors Shachar Lovett, Sasha Sodin

Publication date 25 September 2008

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

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

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)

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.

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

Cites work

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

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)