Random Restrictions and Fourier Concentration 1
summary
Proves the KKL lower bound that a balanced Boolean function has some variable influence at least constant times log n / n, using random restrictions and Fourier analysis rather than combinatorics. Builds a random process (pick live coordinates j with probability μ, fix others z) that pushes high-degree Fourier mass down to Fourier level-one concentration; restricted functions become dictatorships, partitioning inputs so edge-counting and isoperimetric bounds force total influence ≳ log n, which yields the stated individual influence.
AI-written summary · about