Chapter 2 exercises

  1. For each function in Exercise 1.1, determine if it is odd, transitive-symmetric, and/or symmetric.
  2. Show that the $n$-bit functions majority, AND, OR, $\pm \chi_i$, and $\pm 1$ are all linear threshold functions.
  3. Prove May’s Theorem:

    1. 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$.
    2. 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$.
  4. 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|$.
  5. 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$ (anti-monotone in the $i$th direction). We say that $f$ is unate if it is unate in all $n$ directions.

    1. Show that $|\widehat{f}(i)| \leq \mathbf{Inf}_i[f]$ with equality if and only if $f$ is unate in the $i$th direction.
    2. Show that the second statement of Theorem 32 holds even for all unate $f$.
  6. Show that linear threshold functions are unate.
  7. For each function $f$ in Exercise 1.1, compute $\mathbf{Inf}_1[f]$.
  8. 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]$.
  9. 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}}]$.
  10. 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}]]$.
  11. Let $w \in {\mathbb N}$, $n = w 2^w$, and write $f$ for $\mathrm{Tribes}_{w,2^w} : \{-1,1\}^n \to \{-1,1\}$.

    1. Compute $\mathop{\bf E}[f]$ and $\mathop{\bf Var}[f]$, and estimate them asymptotically in terms of $n$.
    2. Describe the function $\mathrm{D}_1 f$.
    3. Compute $\mathbf{Inf}_1[f]$ and $\mathbf{I}[f]$ and estimate them asymptotically.
  12. Prove Proposition 23.
  13. Prove Proposition 25.
  14. Prove Proposition 36.

  15. ½. 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}.

  16. 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}})]$.
  17. 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]$?
  18. 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_{i-1}, {\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}})]$.
    1. Show that $\mathbf{Inf}_i[\mathrm{Maj}_n] = \binom{n-1}{\frac{n-1}{2}}2^{1-n}$ for all $i \in [n]$.
    2. Show that $\mathbf{Inf}_1[\mathrm{Maj}_n]$ is a decreasing function of (odd) $n$.
    3. 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})$.
    4. Deduce that $2/\pi \leq \mathbf{W}^{1}[\mathrm{Maj}_n] \leq 2/\pi + O(n^{-1})$.
    5. Deduce that $\sqrt{2/\pi}\sqrt{n} \leq \mathbf{I}[\mathrm{Maj}_n] \leq \sqrt{2/\pi}\sqrt{n} + O(n^{-1/2})$.
    6. 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}_{n-1}] = \sqrt{2/\pi}\sqrt{n} + O(n^{-1/2})$.
  19. 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.
  20. 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.)
  21. Deduce $\mathrm{T}_\rho f(x) = \sum_{S} \rho^{|S|} \widehat{f}(S)\,x^S$ using Exercise 1.5.
  22. For each function $f$ in Exercise 1.1, compute $\mathbf{I}[f]$.
  23. Which functions $f : \{-1,1\}^n \to \{-1,1\}$ with $\#\{x : f(x) = 1\} = 3$ maximize $\mathbf{I}[f]$?
  24. 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]$.
  25. 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]\}$.

    1. Use the Poincaré Inequality to show $\mathbf{MaxInf}[f] \geq 1/n$.
    2. 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}$.

11 comments to Chapter 2 exercises

Leave a Reply




You can use most standard LaTeX, as well as these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>