Logarithmic reduction of the level of randomness in some probabilistic geometric constructions

DOI10.1016/J.JFA.2005.11.003MaRDI QIDQ2491601zbMATH OpenOpenAlexFDO

Authors S. Artstein-Avidan, Vitali Milman

Publication date 29 May 2006

Published in Journal of Functional Analysis (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jfa.2005.11.003

zbMATH Keywords

asymptotic geometric analysisexplicit constructionsrandomness reductionsections of \(\ell_{1}\)

Mathematics Subject Classification ID

Probabilistic methods in Banach space theory (46B09) Random convex sets and integral geometry (aspects of convex geometry) (52A22) Sums of independent random variables; random walks (60G50)

Review text

Many surprising and sometimes counter-intuitive phenomena in high-dimensional convex geometry are established using probabilistic arguments. Therefore they typically show the existence of certain geometric structures but do not yield explicit constructions. In this paper, the authors show that in many of these results the random steps can be replaced by explicit algorithmic steps. As the main tool, random walks on expander graphs are used.

Recommendations

• scientific article; zbMATH DE number 1182927
• scientific article; zbMATH DE number 18979
• On using deterministic functions to reduce randomness in probabilistic algorithms
• Randomized geometric algorithms and pseudorandom generators
• Explicit dimension reduction and its applications

Cites work

• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• A better approximation for balls
• A Chernoff Bound for Random Walks on Expander Graphs
• Almost Euclidean Quotient Spaces of Subspaces of a Finite-Dimensional Normed Space
• Derandomized graph products
• Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
• Entropy numbers of diagonal operators between symmetric Banach spaces
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Geometric applications of Chernoff-type estimates and a ZigZag approximation for balls
• Global versus local asymptotic theories of finite-dimensional normed spaces
• scientific article; zbMATH DE number 3944537 (Why is no real title available?)
• scientific article; zbMATH DE number 3975773 (Why is no real title available?)
• scientific article; zbMATH DE number 4052452 (Why is no real title available?)
• scientific article; zbMATH DE number 4061904 (Why is no real title available?)
• scientific article; zbMATH DE number 4063946 (Why is no real title available?)
• scientific article; zbMATH DE number 48345 (Why is no real title available?)
• scientific article; zbMATH DE number 194093 (Why is no real title available?)
• scientific article; zbMATH DE number 3487716 (Why is no real title available?)
• scientific article; zbMATH DE number 3551404 (Why is no real title available?)
• scientific article; zbMATH DE number 2152968 (Why is no real title available?)
• scientific article; zbMATH DE number 2121181 (Why is no real title available?)
• On Polyhedral Approximations of the Second-Order Cone
• Ramanujan graphs
• Random embeddings of Euclidean spaces in sequence spaces
• Random Euclidean embeddings in spaces of bounded volume ratio
• Regularization of star bodies by random hyperplane cut off
• Special orthogonal splittings of \(L_1^{2k}\)
• Subspaces of Small Codimension of Finite-Dimensional Banach Spaces
• The dimension of almost spherical sections of convex bodies
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(5)

• Tail Estimates for Sums of Variables Sampled by a Random Walk
• ALMOST EUCLIDEAN SECTIONS OF THE N-DIMENSIONAL CROSS-POLYTOPE USING O(N) RANDOM BITS
• Explicit Euclidean embeddings in permutation invariant normed spaces
• A Remark on Projections of the Rotated Cube to Complex Lines
• Using Rademacher permutations to reduce randomness

This page was built for publication: Logarithmic reduction of the level of randomness in some probabilistic geometric constructions

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