Decision Trees and Influences of Variables Over Product Probability Spaces

Source abstract

A celebrated theorem of Friedgut says that every function f : {0, 1} n → {0, 1} can be approximated by a function g : {0, 1} n → {0, 1} with $\|f-g\|_2^2 \leq \epsilon$ , which depends only on e O ( I f / ε) variables, where I f is the sum of the influences of the variables of f . Dinur and Friedgut later showed that this statement also holds if we replace the discrete domain {0, 1} n with the continuous domain [0, 1] n , under the extra assumption that f is increasing. They conjectured that the condition of monotonicity is unnecessary and can be removed. We show that certain constant-depth decision trees provide counter-examples to the Dinur–Friedgut conjecture. This suggests a reformulation of the conjecture in which the function g : [0, 1] n → {0, 1}, instead of depending on a small number of variables, has a decision tree of small depth. In fact we prove this reformulation by showing that the depth of the decision tree of g can be bounded by e O ( I f / ε 2 ) . Furthermore, we consider a second notion of the influence of a variable, and study the functions that have bounded total influence in this sense. We use a theorem of Bourgain to show that these functions have certain properties. We also study the relation between the two different notions of influence.