Kahn–Kalai–Linial theorem
Statement
Say you have some boolean-valued function
By Poincaré’s inequality, we know that the total influence
The Kahn–Kalai–Linial theorem improves on this
We can then use this bound when
Low variance
When the variance is very small, we can use the edge-isoperimetric inequality to get a better bound on
so
This beats KKL when
This is tight for the tribes function.
Proof
We give two proofs, which only differ in the “midpoint” they pick
- the first looks at the stable total influence
, and is the most intuitive; - the second goes deeper down to the norms of the derivatives
, and makes clear exactly where we use the fact that outputs boolean values.
By stable influence
In summary:
- if the total influence is small, then it must be stable;
- but small influences are unstable under noise;
- so there must be some large influences.
Recall that the total influence is the “expected degree” (weighted by Fourier weight)
whereas the variance represents the amount of weight at positive degree
Intuitively, the fact that
Concretely, by Markov’s inequality, there can’t be more than
In particular, as long as
On the other hand, by small-set expansion, we know that small influences are unstable:
so if every influence is small, the total stable influence must be small compared to the total influence:
Combining both bounds, we get
By derivative norms
To be completely honest, this turned out less insightful than I’d hoped.
For simplicity, here let’s assume that
The stable influences are defined as the stability of the corresponding derivative, which by hypercontractivity we can upper bound by a lower-order1 norm:
so we overall get
On the other hand, the second-order norm of
so we have
So far, everything we’ve said applies equally to real-valued functions. For those, there is nothing contradictory with having
The key thing is that when
Therefore, you can combine the two inequalities and get
This is false for real-valued functions
Consider
It’s clear from its expression that
while the variance is
so
Similarly, by independence, the entropy deficit
-
The stability multiplies the function with (a noisy version) of itself, so we can see it as a kind of squared
-norm, whereas is the squared -norm. ↩