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

DOI10.1142/S0219199708002879zbMath1161.46010arXivmath/0701102MaRDI QIDQ3526528

Sasha Sodin, Shachar Lovett

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

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

Related Items (3)

A counterexample to a strengthening of a question of V. D. Milman ⋮ Explicit Euclidean embeddings in permutation invariant normed spaces ⋮ Zonoids and sparsification of quantum measurements

Cites Work

• A limit theorem for the norm of random matrices
• Entropy numbers of diagonal operators between symmetric Banach spaces
• The dimension of almost spherical sections of convex bodies
• Derandomized graph products
• 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
• Sampling convex bodies: a random matrix approach
• Expander graphs and their applications
• A fast and simple randomized parallel algorithm for the maximal independent set problem

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