摘要：We give a simple proof of the OSSS inequality (O’Donnell, Saks, Schramm, Servedio, FOCS 2005). The inequality states that for any decision tree $T$ calculating a Boolean function $f:\zo^n\rightarrow \oo$, we have $\Var[f] \leq \sum_i \delta_i(T)\Inf_i(f)$, where $\delta_i(T)$ is the probability that the input variable $x_i$ is read by $T$ and $\Inf_i(f)$ is the influence of the $i$th variable on $f$.
关键词：probability; computational complexity; decision trees
