# Random restrictions and the connection to total influence of Boolean functions

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?

• $\delta$ is a constant between 0 and 1 and doesn't depend on n? Jun 2 '14 at 20:37
• Yes. Indeed $\delta\in[0,1]$. Jun 2 '14 at 20:38
• 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.
– 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.