Concentration of Measure Phenomena
2020-10-19..2020-10-22
-- online --
[Functional Inequalities in Discrete Spaces with Applications 2013, Neo-Classical Methods in Discrete Analysis 2013, Approximate Counting, Markov Chains and Phase Transitions, Information Theory, Learning and Big Data (Simons Institute, 2015), Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017), Random Instances and Phase Transitions (Simons Institute, 2016)]
| title | author | length |
|---|---|---|
| Aspects of Coulomb Gases | Djalil Chafai | 59m |
Defines Coulomb kernel for general d, highlights the logarithmic kernel in 2D as singular and long-range, and shows equilibrium measure as the unique minimizer… | ||
| Tail and Moment Bounds for Gaussian Chaoses in Banach Spaces | Rafal Latala | 58m |
Provides two-sided Lp moment and tail bounds for homogeneous Gaussian chaoses of order d with Banach-space–valued coefficients, showing the Lp norm expands as… | ||
| Projections of Probability Distributions: A Measure-Theoretic Dvoretzky Theorem | Elizabeth Meckes | 46m |
Result states that under isotropic and mild shell/concentration assumptions one-dimensional and k-dimensional random projections converge to Gaussian for k up… | ||
| Sharp Isoperimetric Inequalities for Affine Quermassintegrals | Emanuel Milman | 59m |
Proves sharp lower bounds for the affine quermassintegrals, resolves Lutwak's conjecture for all k with equality only for ellipsoids, by showing each affine… | ||
| Poincaré Inequalities and Convergence to Equilibrium with Variable Curvature Bounds | Max Fathi | 49m |
Shows how a uniform curvature lower bound is replaced by a variable or averaged curvature to get quantitative Poincaré constants and convergence rates: proves… | ||
| On Some Brunn-Minkowski Inequalities for Probability Measures Under Symmetry | Galyna Livshyts | 53m |
Proposes a local normal flow approach that reduces Brunn–Minkowski–type concavity to bounding f''/f' for small Minkowski deformations, uses the… | ||
| An Improved Lower Bound for Sparse Reconstruction from Subsampled Hadamard Matrices | Shravas Rao | 51m |
Claim: subsampled Hadamard matrices require about k log k log n rows to satisfy the restricted isometry property for k‑sparse recovery. Proof uses indicator… | ||
| Recent Advances in Algorithmic Heavy-Tailed Statistics | Sam Hopkins | 01h 01m |
Constructs a polynomial-time estimator for heavy-tailed covariance with operator-norm error about sqrt(d/n)·log(1/δ)^{1/4} + sqrt(log(1/δ)/n} under a… | ||
| A Probabilistic Mechanism for Quark Confinement | Sourav Chatterjee | 59m |
Claims that strong mass gap (exponential decay of truncated correlations under arbitrary boundary conditions) together with a nontrivial center symmetry… | ||
| From Gaussian Measure to Partial Colorings and Linear Size Sparsifiers | Thomas Rothvoß | 55m |
Proves a simple two-line polynomial algorithm: project a Gaussian onto K∩[-ε,ε]^n (convex program) and show with Gaussian concentration and a width inequality… | ||
| Random Concave Functions on an Equilateral Lattice with Periodic Hessians | Hari Narayanan | 46m |
Characterizes all concave functions on the equilateral triangular lattice whose second differences (Hessians) repeat periodically, proves existence and… | ||
| Reducing Isotropy to KLS, A Faster Sampling Algorithm | Yin Tat Lee | 50m |
Claims a sampling algorithm that uses roughly n^{3.5} oracle calls for any convex body and, if the KLS conjecture holds, improves to n^{3}. It builds an… | ||
| Gaussian Regularization of the Pseudospectrum and Numerical Linear Algebra | Nikhil Srivastava | 01h 00m |
Shows that adding a small complex Gaussian regularizes nonnormal spectra: a Toeplitz example has Toeplitz n=100: κ≈10^30 but a tiny random perturbation yields… | ||
| Sharp Thresholds for Random Subspaces, and Applications | Mary Wootters | 01h 03m |
Proves a sharp threshold for local properties of uniformly random subspaces over F_q: there's a rate r so dimension below r almost surely avoids any b-sized… | ||
| Moments of the Distance Between Independent Random Vectors | Krzysztof Oleszkiewicz | 01h 02m |
Proves quantitative reversals of the triangle-integral bound for independent Banach-space-valued vectors and identifies optimal constants: constant 3 for p=1… | ||
| Rates of Normal Approximation for Typical Weighted Sums | Sergey Bobkov | 01h 07m |
Sergey Bobkov, University of Minnesota
https://simons.berkeley.edu/talks/rates-normal-approximation-typical-weighted-sums
Concentration of Measure Phenomena | ||
| The Langevin Algorithm in the Non Smooth Log-Concave Case | Joseph Lehec | 01h 00m |
Proves quantitative convergence for the unadjusted Langevin discretization on log‑concave but possibly non‑smooth potentials, showing explicit step‑size and… | ||
| Sharp Poincare and log-Sobolev Inequalities for the Switch Chain on Regular Bipartite Graphs | Konstantin Tikhomirov | 57m |
Proves the Poincaré (spectral gap) constant for the switch chain on simple d-regular bipartite graphs is Theta(n d) under mild growth assumptions on d (allows… | ||
| Log Concavity and Concentration of Measure on the Discrete Hypercube | Ronen Eldan | 59m |
Defines a usable discrete curvature: a density on {-1,1}^n is beta-semi log-concave if the multilinear (harmonic) extension of its log has Hessian bounded… | ||
| The (Non-)Concentration of the Chromatic Number | Annika Heckel | 51m |
Proves that for G(n, 1/2) there are infinitely many n where the chromatic number is not contained in any interval of length n^{1/2 - ε}, matching known upper… | ||
| Graph Matching in Correlated Random Graphs via Small Subgraph Statistics | Tselil Schramm | 01h 03m |
Gives a quasi-polynomial-time algorithm that recovers the planted permutation between two correlated G(n,p) graphs when gamma is constant (example gamma ≈… | ||
| Lower Estimates of Marginal Density | Mark Rudelson | 49m |
Establishes a concrete lower bound for the marginal density of the uniform cube that depends only on the projected dimension d and not on ambient n, with a… | ||
| nothing matches | ||