Every decision tree has an influential variable
| dc.creator | O'Donnell, Ryan | |
| dc.creator | Saks, Michael | |
| dc.creator | Schramm, Oded | |
| dc.creator | Servedio, Rocco A. | |
| dc.date | 2005-08-16 | |
| dc.date.accessioned | 2026-07-07T03:23:19Z | |
| dc.date.available | 2026-07-07T03:23:19Z | |
| dc.description | We prove that for any decision tree calculating a boolean function $f:\{-1,1\}^n\to\{-1,1\}$, \[ \Var[f] \le \sum_{i=1}^n δ_i \Inf_i(f), \] where $δ_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 $Ω(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 $Ω(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 $Ω(v^{4/3})$ bound of Hajnal and is sometimes superior to the best known lower bounds of Chakrabarti-Khot and Friedgut-Kahn-Wigderson. | |
| dc.description | This paper is posted by permission from the IEEE Computer Society. To appear in FOCS 2005 | |
| dc.identifier | https://arxiv.org/abs/cs/0508071 | |
| dc.identifier | http://arxiv.org/abs/cs/0508071 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/32901 | |
| dc.subject | Computational Complexity | |
| dc.subject | Discrete Mathematics | |
| dc.subject | Probability | |
| dc.title | Every decision tree has an influential variable | |
| dc.type | text |