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.