Chapter 4 exercises

1. Show there exists $S \subseteq [n]$ with $|S| \leq \log(s) + O(1)$ and $|\widehat{f}(S)| \geq \Omega(1/s)$. (Hint: use Proposition 9 and Exercise 3.29.)
2. Let $\mathcal{C}$ be the concept class of functions $: \{-1,1\}^n \to \{-1,1\}$ computable by DNF formulas of size at most $s$. Show that $\mathcal{C}$ is learnable using queries with error $\tfrac{1}{2} – \Omega(1/s)$ in time $\mathrm{poly}(n, s)$. (Such a result, with error bounded away from $\tfrac{1}{2}$, is called weak learning.)

1. Show that the parity function $\chi_{[n]} : \{-1,1\}^n \to \{-1,1\}$ can be computed by a DNF (or a CNF) of size $2^{n-1}$.
2. Show that the bound $2^{n-1}$ above is exactly tight. (Hint: show that every term must have width exactly $n$.)
3. Show that there is a depth-$3$ circuit of size $O(n^{1/2}) \cdot 2^{n^{1/2}}$ computing $\chi_{[n]}$. (Hint: break up the input into $n^{1/2}$ blocks of size $n^{1/2}$ and use part (a) twice. How can you compress the result from depth $4$ to depth $3$?)
4. More generally, show there is a depth-$d$ circuit of size $O(n^{1-1/(d-1)}) \cdot 2^{n^{1/(d-1)}}$ computing $\chi_{[n]}$.

Consider the following randomized algorithm which tries to produce an input ${\boldsymbol{x}} \in f^{-1}(\mathsf{True})$. First choose a random permutation $\boldsymbol{\pi} \in S_n$. Then for $i = 1, \dots, n$: If the single-literal clause $x_{\boldsymbol{\pi}(i)}$ appears in $C$ then set $x_{\boldsymbol{\pi}(i)} = \mathsf{True}$, syntactically simplify $C$ under this setting, and say that coordinate $\boldsymbol{\pi}(i)$ is “forced”. Similarly, if the single-literal clause $\overline{x}_{\boldsymbol{\pi}(i)}$ appears in $C$ then set $x_{\boldsymbol{\pi}(i)} = \mathsf{False}$, syntactically simplify $C$, and say that $\boldsymbol{\pi}(i)$ is “forced”. If neither holds, set ${\boldsymbol{x}}_{\pi(i)}$ uniformly at random. If $C$ ever contains two single-literal clauses $x_j$ and $\overline{x}_j$, the algorithm “gives up” and outputs ${\boldsymbol{x}} = \bot$.

1. Show that if ${\boldsymbol{x}} \neq \bot$ then $f({\boldsymbol{x}}) = \mathsf{True}$.
2. For $x \in f^{-1}(\mathsf{True})$ let $p(x) = \mathop{\bf Pr}[{\boldsymbol{x}} = x]$. For $j \in [n]$ let $\boldsymbol{I}_j$ be the indicator random variable for the event that coordinate $j \in [n]$ is forced. Show that $p(x) = \mathop{\bf E}[\prod_{j=1}^n (1/2)^{1-\boldsymbol{I}_j}]$.
3. Deduce $2^n p(x) \geq 2\sum_{j=1}^n \mathop{\bf E}[\boldsymbol{I}_j]$.
4. Show that for every $x$ with $f(x) = \mathsf{True}$, $f(x^{\oplus j}) = \mathsf{False}$ it holds that $\mathop{\bf E}[\boldsymbol{I}_j \mid {\boldsymbol{x}} = x] \geq 1/w$.
5. Deduce $\mathbf{I}[f] \leq w$.

1. Fix an input $x \in \{-1,1\}^n$ and define $u = (\sum_{i=1}^n x_i)/\sqrt{n} \in [-\sqrt{n}, \sqrt{n}]$. Let $\boldsymbol{T}_j$ be the event that the $j$th term of $\boldsymbol{\varphi}$ is made $1$ (logical $\mathsf{False}$) by $x$. Compute $\mathop{\bf Pr}[\boldsymbol{T}_j]$ and $\mathop{\bf Pr}[\boldsymbol{\varphi}(x) = 1]$, and show that the latter is at least $10^{-9}$ assuming $|u| \leq 2$.
2. Let $\boldsymbol{U}_j$ be the event that the $j$th term of $\boldsymbol{\varphi}$ has exactly one $1$ on input $x$. Show that $\mathop{\bf Pr}[\boldsymbol{U}_j \mid \boldsymbol{V}_j] \geq \Omega(w 2^{-w})$ assuming $|u| \leq 2$.
3. Suppose we condition on $\boldsymbol{\varphi}(x) = 1$; i.e., $\cup_{j} \boldsymbol{V}_j$. Argue that the events $\boldsymbol{U}_j$ are independent. Further, argue that for the $\boldsymbol{U}_j$’s which do occur, the indices of their uniquely-$1$ variables are independent and uniformly random among the $1$’s of $x$.
4. Show that $\mathop{\bf Pr}[\mathrm{sens}_{\boldsymbol{\varphi}}(x) \geq c \sqrt{n} \mid \boldsymbol{\varphi}(x) = 1] \geq 1- 10^{-10}$ for $c > 0$ a sufficiently small constant.
5. Show that $\mathop{\bf Pr}_{{\boldsymbol{x}}}[|(\sum_{i=1}^n {\boldsymbol{x}}_i)/\sqrt{n}| \leq 2] \geq \Omega(1)$.
6. Deduce that there exists a monotone function $f : \{-1,1\}^n \to \{-1,1\}$ with the property that $\mathop{\bf Pr}_{{\boldsymbol{x}}}[\mathrm{sens}_f({\boldsymbol{x}}) \geq c' \sqrt{n}] \geq c’$ for some universal constant $c’ > 0$.
7. Both $\mathrm{Maj}_n$ and the function $f$ from the previous exercise have average sensitivity $\Theta(\sqrt{n})$. Contrast the “way” in which this occurs for the two functions.

1. Suppose $R = (J \mid z)$ is a “bad” restriction, meaning that $\phi_{J \mid z}$ is not a constant function. Let $i$ be minimal such that $(T_i)_{J \mid z}$ is neither constantly $\mathsf{True}$ or $\mathsf{False}$, and let $j$ be minimal such that $x_j$ or $\overline{x}_j$ appears in this restricted term. Show there is a unique restriction $R’ = (J \setminus \{j\} \mid z’)$ extending $R$ which does not falsify $T_i$.
2. Suppose we enumerate all bad restrictions $R$, and for each we write down the associated $R’$ as in (a). Show that no restriction is written more than $w$ times.
3. If $(\boldsymbol{J} \mid \boldsymbol{z})$ is a $\delta$-random restriction and $R$ and $R’$ are as in (a), show that $\mathop{\bf Pr}[(\boldsymbol{J} \mid \boldsymbol{z}) = R] = \frac{2\delta}{1-\delta} \mathop{\bf Pr}[(\boldsymbol{J} \mid \boldsymbol{z}) = R']$.
4. Complete the proof by showing $\mathop{\bf Pr}[(\boldsymbol{J} \mid \boldsymbol{z}) \text{ is bad}] \leq 3\delta w$.

1. Show by induction on $d \geq 2$ that any $f : \{-1,1\}^n \to \{-1,1\}$ computable by a $(d,w,s’)$-circuit satisfies $\mathbf{I}[f] \leq w O(\log s’)^{d-2}$.
2. Deduce Theorem 30.