
Chapter 2 exercises
 For each function in Exercise 1.1, determine if it is odd, transitivesymmetric, and/or symmetric.
 Show that the $n$bit functions majority, AND, OR, $\pm \chi_i$, and $\pm 1$ are all linear threshold functions.
 Prove May’s Theorem:
 Show that $f : \{1,1\}^n \to \{1,1\}$ is symmetric and monotone if and only if it can be expressed as a weighted majority with $a_1 = a_2 = \cdots = a_n = 1$.
 Suppose $f : \{1,1\}^n \to \{1,1\}$ is symmetric, monotone, and odd. Show that $n$ must be odd, and that $f = \mathrm{Maj}_n$.
 Subset $A \subseteq \{1,1\}^n$ is called a Hamming ball if $A = \{x : \mathrm{Dist}(x,z) < r\}$ for some $z \in \{1,1\}^n$ and real $r$. Show that $f : \{1,1\}^n \to \{1,1\}$ is the indicator of a Hamming ball if and only if it’s expressible as a linear threshold function $f(x) = \mathrm{sgn}(a_0 + a_1 x_1 + \cdots + a_n x_n)$ with $a_1 = a_2 = \cdots = a_n$.
 Let $f : \{1,1\}^n \to \{1,1\}$ and $i \in [n]$. We say that $f$ is unate in the $i$th direction if either $f(x^{(i \mapsto 1)}) \leq f(x^{(i \mapsto 1)})$ for all $x$ (monotone in the $i$th direction) or $f(x^{(i \mapsto 1)}) \geq f(x^{(i\mapsto 1)})$ for all $x$ (antimonotone in the $i$th direction). We say that $f$ is unate if it is unate in all $n$ directions.
 Show that $\widehat{f}(i) \leq \mathbf{Inf}_i[f]$ with equality if and only if $f$ is unate in the $i$th direction.
 Show that the second statement of Theorem 32 holds even for all unate $f$.
 Show that linear threshold functions are unate.
 For each function $f$ in Exercise 1.1, compute $\mathbf{Inf}_1[f]$.
 Let $f : \{0,1\}^6 \to \{1,1\}$ be given by the weighted majority $f(x) = \mathrm{sgn}(58 + 31x_1 + 31x_2 + 28x_3 + 21x_4 + 2x_5 + 2x_6)$. Compute $\mathbf{Inf}_i[f]$ for all $i \in [6]$.
 Say that coordinate $i$ is $b$pivotal for $f : \{1,1\}^n \to \{1,1\}$ on input $x$ (for $b \in \{1,1\}$) if $f(x) = b$ and $f(x^{\oplus i}) \neq b$. Show that $\mathop{\bf Pr}_{{\boldsymbol{x}}}[i \text{ is } b\text{pivotal on } {\boldsymbol{x}}] = \tfrac{1}{2} \mathbf{Inf}_i[f]$. Deduce that $\mathbf{I}[f] = 2 \mathop{\bf E}_{{\boldsymbol{x}}}[\#\ b\text{pivotal coordinates on } {\boldsymbol{x}}]$.
 Let $\boldsymbol{f} : \{1,1\}^n \to \{1,1\}$ be a random function (as in Exercise 1.8). Compute $\mathop{\bf E}[\mathbf{Inf}_1[\boldsymbol{f}]]$ and $\mathop{\bf E}[\mathbf{I}[\boldsymbol{f}]]$.
 Let $w \in {\mathbb N}$, $n = w 2^w$, and write $f$ for $\mathrm{Tribes}_{w,2^w} : \{1,1\}^n \to \{1,1\}$.
 Compute $\mathop{\bf E}[f]$ and $\mathop{\bf Var}[f]$, and estimate them asymptotically in terms of $n$.
 Describe the function $\mathrm{D}_1 f$.
 Compute $\mathbf{Inf}_1[f]$ and $\mathbf{I}[f]$ and estimate them asymptotically.
 Prove Proposition 23.
 Prove Proposition 25.
 Prove Proposition 36.
 ½. Let $f : \{1,1\}^n \to {\mathbb R}$. Show that
\[
\mathrm{L}f(x) = \frac{d}{d \rho} \mathrm{T}_{\rho}f(x)\Bigr_{\rho = 1} = \frac{d}{dt} \mathrm{T}_{e^{t}} f(x) \Bigr_{t = 0}.
\]
 Suppose $f, g : \{1,1\}^n \to {\mathbb R}$ have the property that $f$ does not depend on the $i$th coordinate and $g$ does not depend on the $j$th coordinate ($i \neq j$). Show that $\mathop{\bf E}[{\boldsymbol{x}}_i {\boldsymbol{x}}_j f({\boldsymbol{x}}) g({\boldsymbol{x}})] = \mathop{\bf E}[\mathrm{D}_j f({\boldsymbol{x}}) \mathrm{D}_i g({\boldsymbol{x}})]$.
 For $f : \{1,1\}^n \to \{1,1\}$ we have that $\mathop{\bf E}[\mathrm{sens}_f({\boldsymbol{x}})] = \mathop{\bf E}_{\boldsymbol{S} \sim \mathscr{S}_{f}}[\boldsymbol{S}]$. Show that also $\mathop{\bf E}[\mathrm{sens}_f({\boldsymbol{x}})^2] = \mathop{\bf E}[\boldsymbol{S}^2]$ (hint: use Proposition 36). Is it true that $\mathop{\bf E}[\mathrm{sens}_f({\boldsymbol{x}})^3] = \mathop{\bf E}[\boldsymbol{S}^3]$?
 For $f : \{1,1\}^n \to {\mathbb R}$, define $\mathrm{Var}_i f : \{1,1\}^n \to {\mathbb R}$ by $\mathrm{Var}_i f(x) = \mathop{\bf Var}_{{\boldsymbol{x}}_i}[f(x_1, \dots, x_{i1}, {\boldsymbol{x}}_i, x_{i+1}, \dots, x_n)]$. Show that $\mathbf{Inf}_i[f] = \mathop{\bf E}_{{\boldsymbol{x}}}[\mathrm{Var}_i f({\boldsymbol{x}})]$.

 Show that $\mathbf{Inf}_i[\mathrm{Maj}_n] = \binom{n1}{\frac{n1}{2}}2^{1n}$ for all $i \in [n]$.
 Show that $\mathbf{Inf}_1[\mathrm{Maj}_n]$ is a decreasing function of (odd) $n$.
 Use Stirling’s formula $m! =(m/e)^m(\sqrt{2\pi m} + O(m^{1/2}))$ to deduce that $\mathbf{Inf}_1[\mathrm{Maj}_n] = \frac{\sqrt{2/\pi}}{\sqrt{n}} + O(n^{3/2})$.
 Deduce that $2/\pi \leq \mathbf{W}^{1}[\mathrm{Maj}_n] \leq 2/\pi + O(n^{1})$.
 Deduce that $\sqrt{2/\pi}\sqrt{n} \leq \mathbf{I}[\mathrm{Maj}_n] \leq \sqrt{2/\pi}\sqrt{n} + O(n^{1/2})$.
 Suppose $n$ is even and $f : \{1,1\}^n \to \{1,1\}$ is a majority function. Show that $\mathbf{I}[f] = \mathbf{I}[\mathrm{Maj}_{n1}] = \sqrt{2/\pi}\sqrt{n} + O(n^{1/2})$.
 Using only Cauchy–Schwarz and Parseval, give a very simple proof of the following weakening of Theorem 32: If $f : \{1,1\}^n \to \{1,1\}$ is monotone then $\mathbf{I}[f] \leq \sqrt{n}$. Extend also to the case of $f$ unate.
 Prove Proposition 57 with $O(n^{1})$ in place of $o_n(1)$. (Hint: show $\widehat{f}(i) \leq \frac{\sqrt{2/\pi}}{\sqrt{n}} + O(n^{3/2})$ using Theorem 32.)
 Deduce $\mathrm{T}_\rho f(x) = \sum_{S} \rho^{S} \widehat{f}(S)\,x^S$ using Exercise 1.5.
 For each function $f$ in Exercise 1.1, compute $\mathbf{I}[f]$.
 Which functions $f : \{1,1\}^n \to \{1,1\}$ with $\#\{x : f(x) = 1\} = 3$ maximize $\mathbf{I}[f]$?
 Suppose $f : \{1,1\}^n \to {\mathbb R}$ is an even function (recall Exercise 1.9). Show the improved Poincaré inequality $\mathop{\bf Var}[f] \leq \tfrac{1}{2} \mathbf{I}[f]$.
 Let $f : \{1,1\}^n \to \{1,1\}$ be unbiased, $\mathop{\bf E}[f] = 0$, and let $\mathbf{MaxInf}[f]$ denote $\max_{i \in [n]}\{\mathbf{Inf}_i[f]\}$.
 Use the Poincaré Inequality to show $\mathbf{MaxInf}[f] \geq 1/n$.
 Prove that $\mathbf{I}[f] \geq 2 – n \mathbf{MaxInf}[f]^2$. (Hint: prove $\mathbf{I}[f] \geq \mathbf{W}^{1}[f] + 2(1\mathbf{W}^{1}[f])$ and use Exercise 5.) Deduce that $\mathbf{MaxInf}[f] \geq \frac{2}{n} – \frac{4}{n^2}$.


Small typo: sgn(a_0+a_1 x_1 \cdots + a_n x_n), x_n missing.
Question 4, Small typo: sgn(a_0+a_1 x_1 \cdots + a_n x_n), x_n missing.
Fixed, thanks!
Hi Ryan
in ex 19 i see some latex code (see Exercise {ex:deg1vsinf})
thanks
I think the link in Ex. 13 is broken.
In Ex. 17 $f$ needs to be boolean, rather than just real valued.
Sorry Ex 17 is fine
Hi Noam — yeah, I think Ex 17 is okay, but thanks re the broken link on Exercise 13! I fixed it.
r
Small typo in Exercise 2.8 (p. 46 in the book): stray “?” at the end of the hint.
Thanks!