High Dimensional Geometry and Concentration II
summary
Proves the functional Brunn–Minkowski (Prékopa–Leindler) inequality by induction on dimension, using Brunn–Minkowski only in the one‑dimensional base case, then applies it once with F=1_A·γ, G=exp(dist(x,A)^2/4)·γ and H=γ to get the Gaussian measure bound that γ(A)·γ(A_T^c) ≤ exp(−T^2/4), i.e. exponential concentration. Gives a quantitative Dvoretzky result: worst‑case near‑Euclidean sections have dimension Θ(C(ε)·log n), with L1 ⇒ Θ(n) and L∞ ⇒ Θ(log n); proof picks a random section + epsilon-net and uses Levy. Central tool named Prékopa–Leindler.
AI-written summary · about
chapters (6)
- 0:00Introduction to generalizations
- 1:20Inductive proof
- 13:04Concentration on Gaussians
- 25:04Symmetric convex bodies
- 31:02Large Euclidean sections
- 50:33Isoperimetric inequality
related talks
01h 34mAlgorithmic High-Dimensional Geometry I
01h 04mHigher-dimensional Expansion of Random Geometric Complexes
49mInfluences in Gaussian Space
01h 11m(Hidden) Symmetries of Computational Problems (continued)
56mTesting Thresholds for High-dimensional Sparse Random Geometric Graphs
48mComputational-Statistical Tradeoffs in Robust High-Dimensional Estimation
01h 34mAlgorithmic High-Dimensional Geometry II
36mPrivately Learning High-Dimensional Distributions