<p><em>Claim:</em> 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})$.</p>

<p><em>Proof sketch:</em>
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$.</p>

<p>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.</p>

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

CC BY-SA 3.0
2014-07-09T09:01:01.830Z
2014-07-09T09:01:01.830Z
Igor Shinkar
<p>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?</p>

CC BY-SA 3.0
2014-06-02T20:37:11.883Z
$\delta$  is a constant between 0 and 1 and doesn't depend on n?
Kaveh
CC BY-SA 3.0
2014-06-02T20:38:30.213Z
Yes. Indeed $\delta\in[0,1]$.
Amit Levi
<cc.complexity-theory><co.combinatorics><circuit-complexity><boolean-functions>
Random restrictions and the connection to total influence of Boolean functions
Amit Levi
# Random restrictions and the connection to total influence of Boolean functions

(Asked by: username_0 on 2014-06-02)

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?

**Tags:** cc.complexity-theory, co.combinatorics, circuit-complexity, boolean-functions

> **Comments:**
> **username_1**: $\delta$  is a constant between 0 and 1 and doesn't depend on n?  
> **username_0**: Yes. Indeed $\delta\in[0,1]$.  

---

## 1 answers

### Answer by username_2 on 2014-07-09. Score: 4 | Accepted answer

*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.


---

