Influences and decision trees
Hamed Hatami · arXiv (Cornell University) · 2006
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 ≤ ǫ which depends only on eO(If/ǫ) variables where If 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 monotone. 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 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 eO(If/ǫ2). AMS Subject Classification: 06E30- 28A35