= Kahn-Kalai-Linial theorem
{c}
{title2=$\max_i I_i(f)\geq c\operatorname{Var}(f)\log(n)/n$}
For a <Boolean function> $f:\{0,1\}^n\to\{0,1\}$ under the uniform <probability measure>, some coordinate has <influence of a variable> at least $c\operatorname{Var}(f)\log(n)/n$, where $c>0$ is an absolute constant and $I_i(f)$ is the probability that flipping coordinate $i$ changes $f$. For <variance> bounded below, this is order $\log(n)/n$. The <tribes function> shows that this order cannot be improved for general balanced <Boolean functions>.
Back to article page
