Every decision tree has an influential variable

Details Every decision tree has an influential variable Every decision tree has an influential variable

2005-08-16

arxiv.org/abs/cs/0508071v1

Computer Science

Computational Complexity

This paper is posted by permission from the IEEE Computer Society. To appear in FOCS 2005

Scientific paper

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 \delta_i \Inf_i(f), \] 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(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 and is sometimes superior to the best known lower bounds of Chakrabarti-Khot and Friedgut-Kahn-Wigderson.

Affiliated with

Also associated with

No associations

Rating

Every decision tree has an influential variable does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Every decision tree has an influential variable, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Every decision tree has an influential variable will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-131005