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
Download article from ToC site:
[PDF (146K)]    [PS (359K)]    [PS.GZ (126K)]    [PS.ZIP (126K)]
[Source ZIP]
Misc.:
[About the Author] [HTML Bibliography] [BibTeX]
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]

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 ] ≤ ∑i δi ( T ) Infi ( f ), where δi ( T ) is the probability that the input variable xi is read by T and Infi ( f ) is the influence of the i-th variable on f.