Maximal Inequalities on the Hypercube

on YouTube ↗50m

" summary

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 an ε-fraction is O(ε) rather than depending on n. Proof combines Stein-style reductions, spectral estimates on the sphere operators via Kravchuk polynomials, a comparison to senate operators, and domination by a noise semigroup (Poisson clocks) plus Cauchy–Schwarz; yields a constant operator norm and therefore the claimed combinatorial corollary.

AI-written summary · about

" chapters (20)

1. 0:00Intro
2. 0:11Talk outline
3. 0:44Motivation 1: An Election Interpretation
4. 4:13Motivation 2: UGC or "Can We Hope for Better Approximation Algorithms in P?"
5. 5:45Unique Games - Unique Label Cover Problem
6. 7:46Unique Games Conjecture
7. 11:12Where to begin if we want to refute UGC?
8. 12:41UGC and the Spectrum of General Graphs
9. 15:33An Algorithm
10. 18:56The Adversary
11. 19:56The Question
12. 21:19The Conjecture
13. 22:30The Challenge
14. 29:13Convert to a problem in Analysis
15. 31:49Maximal Operator
16. 33:51Maximal Inequalities: a little history
17. 38:52Step 2 of Proof
18. 41:32Step 1+ Step 2
19. 42:02Step 1 of Proof
20. 45:03Spherical-Mean Maximal Inequality: method