Say we have a Boolean function $f:\{-1,1\}^n\rightarrow \{-1,1\}$ and we apply $\delta$-random restriction on $f$. In addition, say that the decision tree $T$ that computes $f$ shrinks to size $O(1)$ as a result of the random restriction. Does this imply that $f$ has a very low total-influence?

  • $\begingroup$ $\delta$ is a constant between 0 and 1 and doesn't depend on n? $\endgroup$
    – Kaveh
    Jun 2 '14 at 20:37
  • 1
    $\begingroup$ Yes. Indeed $\delta\in[0,1]$. $\endgroup$
    – Amit Levi
    Jun 2 '14 at 20:38
  • 1
    $\begingroup$ I'm not sure if that's what you are looking for, but by the switching lemma, if a function can be represented by a small-width DNF, then w.h.p. it would shrink to a decision tree of a constant size. Small-width DNFs have low total-influence, and one can express decision trees via DNFs, so morally it seems that this is the case. $\endgroup$
    – user887
    Jun 3 '14 at 8:51

Claim: If $\delta$-random restriction of $f$ has decision tree of size $O(1)$ (in expectation), then the total influence of such $f$ is $O(\delta^{-1})$.

Proof sketch: By definition of influence we have $Inf(f) = n \cdot \Pr_{x,i}[f(x) \neq f(x+e_i)]$. Let us upper bound $\Pr_{x,i}[f(x) \neq f(x+e_i)]$ by first applying a $\delta$-restriction, then picking $i \in [n]$ among the remaining coordinates, and fixing at random everything except for $x_i$.

Now, if $\delta$-restriction reduces the decision tree of $f$ to size $O(1)$, then in particular the $\delta$-restriction of $f$ depends on $r = O(1)$ coordinated. Let us now pick one random unfixed coordinate (among $\delta n$), and fix all others randomly. Since the $\delta$-restriction of $f$ depends on at most $r$ coordinates, we get a function (on one bit) that is not constant with probability at most $\frac{r}{\delta n}$. Therefore $Inf(f) = n \cdot \Pr_{x,i}[f(x) \neq f(x+e_i)] \leq \frac{r}{\delta}$, as required.

Remark: The claim above is tight by taking a parity function on $O(1/\delta)$ bits.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.