Every decision tree has an influential variable

We prove that for any decision tree calculating a boolean function \(f:{-1,1}_n\to {-1,1}\),

where \({\delta }_i\) is the probability that the \(i\)th input variable is read and \(\Inf_i(f)\) is the influence of the \(i\)th variable on \(f\). The variance, influence and probability are taken with respect to an arbitrary product measure on \({-1,1}_n\). It follows that the minimum depth of a decision tree calculating a given balanced function is at least the reciprocal of the largest influence of any input variable. Likewise, any balanced boolean function with a decision tree of depth \(d\) has a variable with influence at least \(\frac{1}{d}\). The only previous nontrivial lower bound known was \(\Omega (d2_{-d})\). Our inequality has many generalizations, allowing us to prove influence lower bounds for randomized decision trees, decision trees on arbitrary product probability spaces, and decision trees with non-boolean outputs. As an application of our results we give a very easy proof that the randomized query complexity of nontrivial monotone graph properties is at least \(\Omega (v_{4/3}/p_{1/3})\), where \(v\) is the number of vertices and \(p \leq \half\) is the critical threshold probability. This supersedes the milestone \(\Omega (v_{4/3})\) bound of Hajnal and is sometimes superior to the best known lower bounds of Chakrabarti-Khot and Friedgut-Kahn-Wigderson.

Opens in a new tab