It ain't over till it's over
summary
Balanced Boolean functions with variance Ω(1) and max influence τ remain nonconstant with overwhelming probability after fixing all but a \tilde{Ω}((log 1/τ)^{-1}) fraction of coordinates (equivalently keeping p ≈ 1/log(1/τ) coordinates alive up to polylog factors); the bound is tight (tribes AND_{n/C log n} ◦ OR_{C log n} witnesses optimality). Proof uses a conditioned random‑restriction/martingale process plus hypercontractivity and KL/divergence entropy estimates and yields nontrivial variance with probability 1−o(1).
AI-written summary · about
chapters (13)
- 0:00Intro
- 1:12Examples
- 3:04Functions with small influences
- 6:00Random restrictions
- 11:04One application
- 14:07Condorcet Method
- 22:22Two random processes
- 30:16Controlled Process
- 38:14Analysis
- 39:35Partial derivatives remain small
- 41:09Switch to continuous process
- 42:59Partial derivatives under uniform process
- 51:46Entropy comparison
related talks
38mAn Information Theoretic View of Hypercontractivity
01h 00mAverage-case Complexity for Polynomials, and All That
38mSome Easy Optimization Problems Have the Overlap-Gap Property
57mStructure Of Boolean Almost Low Degree Functions On The Biased Cube
01h 05mLog-concave Polynomials and Spectral Independence 1
45mTractability And Overparametrization In Some Simple Models
56mLog-concave Polynomials and Spectral Independence 3
44mBeyond Worst-Case: Instance-Dependent Optimality in Reinforcement Learning