Combinatorial Proofs of Concentration Bounds
summary
Gives a direct combinatorial proof that for n independent fair bits the chance of ≥ (1+ε)n/2 ones is ≤ exp(-ε^2 n/10) by choosing a random subset M of size m ≈ ε n/4 and comparing Pr[all bits in M are 1] to Pr[many ones] which yields a (1+ε/2)^m 2^{-m} factor. Extends the method to random walks on λ-expanders to get a tight bound about exp(-((1-λ)/(1+λ))·μ(1-μ)ε^2 n/2) and relates the approach to the nth-moment method and polynomial concentration.
AI-written summary · about
chapters (8)
- 0:00Introduction
- 2:02Outline
- 2:32Proof idea
- 11:47Walks
- 13:25Theorem
- 23:07Expanding Box
- 23:38Connection to Moments
- 25:38Similarities
related talks
30mOn Bounded Depth Proofs For Tseitin Formulas On The Grid; Revisited
35mClique is hard on average for unary Sherali-Adams
22mExecution Time Program Verification With Tight Bounds
01h 16mIn Search of the Hard Instances
59mThe Proof Complexity of Integer Programming
24mA New Conjecture on Hardness of Low-Degree 2-CSP’s with...
21mSupermartingales for Unique Fixed Points: A Unified Approach to Lower Bound Verification
29mGraph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz