R. O'Donnell and Michael Saks and Oded Schramm and R. Servedio.

In this paper we prove a new inequality relating the decision tree complexity and the influences of boolean functions. In particular, we show that 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(d 2^{-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~\cite{Hajnal:91} and is sometimes superior to the best known lower bounds of Chakrabarti-Khot~\cite{ChakrabartiKhot:01} and Friedgut-Kahn-Wigderson~\cite{FKW:02}.

Postscript or pdf of conference version