Theory of Computing
-------------------
Title     : Decision Trees and Influence: an Inductive Proof of the OSSS Inequality
Authors   : Homin K. Lee
Volume    : 6
Number    : 4
Pages     : 81-84
URL       : https://theoryofcomputing.org/articles/v006a004

Abstract
--------

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 : {0,1}^n --> {-1,1}, 

we have

    Var[f]  \le  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.