Volume 6 (2010)
Article 4 pp. 81-84
[Note]

Decision Trees and Influence: an Inductive Proof of the OSSS Inequality

Received: October 23, 2009

Published: August 17, 2010

Published: August 17, 2010

**Keywords:**probability, computational complexity, decision trees

**Categories:**note, complexity theory, Boolean functions, decision tree, sensitivity, influence, OSSS inequality

**ACM Classification:**G.2, G.3, F.1.3

**AMS Classification:**05A20, 60C05, 68R05, 68Q87

**Abstract:**
[Plain Text Version]

$
\DeclareMathOperator{\zo}{\{0,1\}} %bit set
\newcommand{\oo}{\{-1,1\}} %bit set
\DeclareMathOperator*{\Var}{Var}
\DeclareMathOperator{\Inf}{Inf}
$

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$.