We prove that for any decision tree calculating a Boolean function f : {-1,1}/sup n/ /spl rarr/ {-1, 1}, Var[f] /spl les/ /spl Sigma/ /sub i=1/ /sup n/ /spl delta//sup i/Inf/sub i/(f), i = 1 where /spl delta//sup i/ is the probability that the ith input variable is read and Inf/sub i/(f) is the influence of the ith variable on f. The variance, influence and probability are taken with respect to an arbitrary product measure on {-1, 1}/sup n/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 1/d. The only previous nontrivial lower bound known was /spl Omega/(d2/sup -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 nonBoolean 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/spl Omega/(v/sup 4/3//p/sup 1/3/), where v is the number of vertices and p /spl les/ 1/2 is the critical threshold probability. This supersedes the milestone /spl Omega/(v/sup 4/3//p/sup 1/3/) bound of Hajnal (1991) and is sometimes superior to the best known lower bounds of Chakrabarti-Khot (2001) and Friedgut-Kahn-Wigderson (2002).

A Boolean function of n bits is balanced if it takes the value 1 with probability 1⁄2. We exhibit a balanced Boolean function with a randomized evaluation procedure (with probability 0 of making a mistake) so that on uniformly random inputs, no input bit is read with probability more than Θ(n-1/2√ log n). We construct a balanced monotone Boolean function and a randomized algorithm computing it for which each bit is read with probability Θ(n-1⁄3 log n). We then show that for any randomized algorithm for evaluating a balanced Boolean function, when the input bits are uniformly random, there is some input bit that is read with probability at least Θ(n-1𔊪). For balanced monotone Boolean functions, there is some input bit that is read with probability at least Θ(n-1𔊫).