
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 ith variable on f.