Functional Inequalities in Discrete Spaces with Applications 2013
2013-09-30..2013-10-04
Berkeley, United States
as the organisers put it
The goal of this program is to bring together mathematicians and computer scientists to study influences, measures of complexity of discrete functions, functional inequalities, invariance principles, non-classical norms, representation theory and other modern topics in mathematical analysis and their applications to theoretical computer science.
who it's for
theoretical computer scientists, probability theorists, analysis researchers, combinatorics researchers, machine learning researchers, graph algorithm designers, statistical learning theorists
topics
total influence of Boolean functions; Rademacher sums and high frequencies; maximal averages on hypercube; Grothendieck inequality constructions; Johnson-Lindenstrauss for SVMs; concentration for non-Lipschitz functions; strong Rayleigh and determinantal measures; suprema of Bernoulli processes; spectral gap of constrained spin models; discrete Ricci curvature on graphs; displacement convexity of entropy; small-set expansion and Cheeger generalizations
| title | author | length |
|---|---|---|
| A Structure Theorem for Boolean Functions with Small Total Influences | Hamed Hatami | 47m |
A structural theorem says Boolean functions on a product probability space with constant total influence are L2-close to a K-pseudo-junta defined by a family… | ||
| On Mimicking Rademacher Sums | Krzysztof Oleszkiewicz | 01h 00m |
For the discrete cube with fixed cutoff K the L1 distance from the Rademacher sum to the subspace of only high frequencies is Θ(K): an explicit function is… | ||
| Maximal Inequalities on the Hypercube | Alexandra Kolla | 50m |
Proves a dimension-independent L2 bound for the maximal average over Hamming spheres on {0,1}^n, so the number of vertices ruined by an adversary that colours… | ||
| Variants of Parseval's Formula and the Grothendieck Inequality | Ron Blei | 54m |
Constructs a Riesz products-based, explicit continuous injection from the l2 unit ball into L∞(Ω) that registers dot products by an integral, giving a… | ||
| Concentration Inequalites in Learning with Kernels | Devdatt Dubhashi | 44m |
Shows that Johnson–Lindenstrauss preserves margins up to (1+ε) while projecting to k = O(ε^-2 log n) dimensions, so SVM decision boundary and pairwise… | ||
| Concentration Inequalities for Non-Lipschitz Functions | Paweł Wolff | 01h 02m |
Shows that if a vector satisfies a Sobolev-type inequality (e.g. log-Sobolev/Gaussian) then moments and tails of C^d functions are controlled by concrete norms… | ||
| Concentration of Lipschitz Functionals of Determinantal and Other Strong Rayleigh Measures | Yuval Peres | 56m |
Proves that homogeneous measures with the stochastic covering property (including strong Rayleigh/determinantal and balanced matroid laws such as uniform… | ||
| On the Suprema of Bernoulli Processes | Rafal Latala | 53m |
Proves the Bernoulli Conjecture: the expected supremum of a Bernoulli process is equivalent (up to universal constants) to the infimum over decompositions of T… | ||
| Spectral Gap of a Kinetically Constrained Spin Model on Trees: Power Law Scaling at Criticality | Cyrille Roberto | 58m |
Kinetically constrained 0–1 spins on a k‑ary tree use product Bernoulli(p) equilibrium and flip a site only when all children are empty; the bootstrap critical… | ||
| Discrete Ricci Curvature via Convexity of the Entropy | Jan Maas | 56m |
Shows W2 fails on discrete graphs (two‑point case gives no W2 geodesics), so builds a new Riemannian‑type transport metric using a logarithmic mean to pair… | ||
| Displacement Convexity of Entropy on Graphs | Prasad Tetali | 01h 05m |
Defines Mt(A,B) as the set of graph midpoints and builds an explicit interpolation μ_t^π by choosing a random geodesic + binomial sampling with number of… | ||
| On Graph Spectra and Small Set Expansion | Prasad Raghavendra | 59m |
Gives concrete algorithms and constructions: shows you can distinguish small‑set expansion up to a barrier of sqrt(ε log(1/δ)) and proves a higher‑order… | ||
| Two Generalizations of Cheeger's Inequality | Luca Trevisan | 01h 00m |
Claims that Cheeger’s inequality extends to higher eigenvalues: lambda_k small ⇔ k disjoint low‑conductance sets, with a quantitative relation between the… | ||
| On Hyperboundedness and Spectrum of Markov Operators | Laurent Miclo | 53m |
For reversible Markov kernels on a probability space, existence of hyperboundedness (Pt or M mapping L2 into Lp for some p>2) forces a positive spectral gap… | ||
| A Removal Lemma for Kneser Graphs and Product Graphs | Ehud Friedgut | 58m |
Proves a removal lemma for sparse product-type graphs (notably the Kneser graph layer and the triangle-power product graph): any vertex subset that spans at… | ||
| Approximations of Submodular, XOS and Self-Bounding Functions by Juntas | Jan Vondrák | 54m |
Proves a real-valued Friedgut theorem and shows which influence norms control L2 approximation, using hypercontractive inequalities and a boosting lemma… | ||
| Noise Stability and Central Limit Theorem for Random Effective Resistance | Raphaël Rossignol | 56m |
Model assumes IID resistances in [1,Λ] on Z^d and identifies effective conductance ~n^{d-2} (so resistance ~n^{2-d}). Variance has expected lower bound… | ||
| Strong Noise Sensitivity and Random Graphs | Jeffrey Steif | 55m |
Defines strong noise sensitivity via conditioning on a particular one witness and connects it to witness geometry and influences; uses second moment and… | ||
| Majority is Stablest for Dependent Variables | Joe Neeman | 55m |
Extends Majority is Stablest to dependent X,Y by proving for rho-correlated joint laws that E[J(f(X),g(Y))] ≤ J(Ef,Eg) plus an explicit error controlled by the… | ||
| A Two-Sided Estimate for the Gaussian Noise Stability Deficit | Ronen Eldan | 56m |
Proves a quantitative two‑sided bound that controls the Gaussian noise‑stability deficit by a centroid metric (norm difference between Gaussian centers) up to… | ||
| Reversing Hypercontractivity | Elchanan Mossel | 52m |
Shows a uniform reverse hypercontractivity inequality: for any product space and any nonnegative f, T_t raises q‑seminorms above p‑seminorms with no factor… | ||
| Influences in Gaussian Space | Arnab Sen | 49m |
Defines a new geometric influence by integrating one-dimensional boundary (lower Minkowski) measures of coordinate fibers, shows it equals an L∞ surface… | ||
| nothing matches | ||