Every decision tree has an influential variable

Ryan O'Donnell, Michael Saks, Oded Schramm +1

We prove that for any decision tree calculating a boolean function $f:\{-1,1{\}}^n\to \{-1,1\}$, \[ \Var[f] \le \sum_{i=1}^n δ_i \Inf_i(f), \] where ${\delta }_i$ is the probability that the…