Chapter 1 exercises

1. $\max_2 : \{-1,1\}^2 \to \{-1,1\}$, the maximum function on $2$ bits (also known as the logical $\mathrm{AND}$ function);
2. $\min_3 : \{-1,1\}^3 \to \{-1,1\}$ and $\max_3 : \{-1,1\}^3 \to \{-1,1\}$;
3. the indicator function $1_{\{a\}} : {\mathbb F}_2^n \to \{0,1\}$, where $a \in {\mathbb F}_2^n$;
4. the density function $\varphi_{\{a\}} : {\mathbb F}_2^n \to {\mathbb R}^{\geq 0}$, where $a \in {\mathbb F}_2^n$;
5. the density function $\varphi_{\{a, a+e_i\}} : {\mathbb F}_2^n \to {\mathbb R}^{\geq 0}$, where $a \in {\mathbb F}_2^n$ and $e_i = (0, \dots, 0, 1, 0, \dots, 0)$ with the $1$ in the $i$th coordinate;
6. the density function corresponding to the product probability distribution on $\{-1,1\}^n$ in which each coordinate has mean $\rho \in [-1,1]$;
7. the inner product mod $2$ function, $\mathrm{IP}_{2n} : {\mathbb F}_2^{2n} \to \{-1,1\}$ defined by $\mathrm{IP}_{2n}(x_1, \dots, x_n, y_1, \dots, y_n) = (-1)^{x \cdot y}$;
8. the equality function $\mathrm{Equ}_n : \{-1,1\}^n \to \{0,1\}$, defined by $\mathrm{Equ}_n(x) = 1$ if and only if $x_1 = x_2 = \cdots = x_n$;
9. the not-all-equal function $\mathrm{NAE}_n : \{-1,1\}^n \to \{0,1\}$, defined by $\mathrm{NAE}_n(x) = 1$ if and only if the bits $x_1, \dots, x_n$ are not all equal;
10. the selection function $\mathrm{Sel} : \{-1,1\}^3 \to \{-1,1\}$ which outputs $x_2$ if $x_1 = -1$ and outputs $x_3$ if $x_1 = 1$;
11. $\mathrm{mod}_3 : {\mathbb F}_2^3 \to \{0,1\}$ which is $1$ if and only if the number of $1$’s in the input is congruent to $1$ modulo $3$;
12. $\mathrm{OXR} : {\mathbb F}_2^3 \to \{0,1\}$ defined by $\mathrm{OXR}(x_1,x_2,x_3) = x_1 \vee (x_2 \oplus x_3)$. Here $\vee$ denotes logical OR, $\oplus$ denotes logical XOR;
13. the sortedness function $\mathrm{Sort}_4 : \{-1,1\}^4 \to \{-1,1\}$, defined by $\mathrm{Sort}_4(x) = -1$ if and only if $x_1 \leq x_2 \leq x_3 \leq x_4$ or $x_1 \geq x_2 \geq x_3 \geq x_4$;
14. the hemi-icosahedron function $\mathrm{HI} : \{-1,1\}^6 \to \{-1,1\}$, defined as follows: $\mathrm{HI}(x)$ is $1$ if the number of $1$’s in $x$ is $1$, $2$, or $6$. $\mathrm{HI}(x)$ is $-1$ if the number of $-1$’s in $x$ is $1$, $2$, or $6$. Otherwise, $\mathrm{HI}(x)$ is $1$ if and only if one of the ten facets in the following diagram has all three of its vertices $1$:
     
15. the majority functions $\mathrm{Maj}_5 : \{-1,1\}^5 \to \{-1,1\}$ and $\mathrm{Maj}_7 : \{-1,1\}^7 \to \{-1,1\}$;
16. the complete quadratic function $\mathrm{CQ}_n : {\mathbb F}_2^{n} \to \{-1,1\}$ defined by $\mathrm{CQ}_n(x) = \chi(\sum_{1 \leq i < j \leq n} x_ix_j)$. (Hint: determine $\mathrm{CQ}_n(x)$ as a function of the number of $1$’s in the input modulo $4$. You will want to distinguish whether $n$ is even or odd.)

1. Express $\widehat{f^\dagger}(S)$ in terms of $\widehat{f}(S)$.
2. Verify that $f = f^\mathrm{odd} + f^\mathrm{even}$ and that $f$ is odd (respectively, even) if and only if $f = f^\mathrm{odd}$ (respectively, $f = f^\mathrm{even}$).
3. Show that \begin{equation*} f^\mathrm{odd} = \sum_{\substack{S \subseteq [n] \\ |S|\ \mathrm{odd}}} \widehat{f}(S)\,\chi_S, \qquad f^\mathrm{even} = \sum_{\substack{S \subseteq [n] \\ |S|\ \mathrm{even}}} \widehat{f}(S)\,\chi_S. \end{equation*}

1. Using the interpolation method from Section 2, show that every $f : \{\mathsf{False},\mathsf{True}\}^n \to \{\mathsf{False},\mathsf{True}\}$ can be represented as a real multilinear polynomial \begin{equation} \label{eqn:zotzo-poly} q(x) = \sum_{S \subseteq [n]} c_S \prod_{i \in S} x_i, \end{equation} “over $\{0,1\}$”, meaning mapping $\{0,1\}^n \to \{0,1\}$.
2. Show that this representation is unique. (Hint: if $q$ as in \eqref{eqn:zotzo-poly} has at least one nonzero coefficient, consider $q(a)$ where $a \in \{0,1\}^n$ is the indicator vector of a minimal $S$ with $c_S \neq 0$.)
3. Show that all coefficients $c_S$ in the representation \eqref{eqn:zotzo-poly} will be integers in the range $[-2^n, 2^n]$.
4. Let $f : \{\mathsf{False}, \mathsf{True}\}^n \to \{\mathsf{False}, \mathsf{True}\}$. Let $p(x)$ be $f$’s multilinear representation when $\mathsf{False}, \mathsf{True}$ are $1, -1 \in {\mathbb R}$ (i.e., $p$ is the Fourier expansion of $f$) and let $q(x)$ be $f$’s multilinear representation when $\mathsf{False}, \mathsf{True}$ are $0, 1 \in {\mathbb R}$. Show that $q(x) = \tfrac{1}{2} – \tfrac{1}{2} p(1-2x_1, \dots, 1-2x_n)$.

1. Show that $\deg(f) = \deg(a+bf)$ for any $a, b \in {\mathbb R}$ (assuming $b \neq 0$, $a+bf \neq 0$).
2. Show that $\deg(f) \leq k$ if and only if $f$ is a real linear combination of functions $g_1, \dots, g_s$, each of which depends on at most $k$ input coordinates.
3. Which functions in Exercise 1 have “nontrivial” degree? (Here $f : \{-1,1\}^n \to {\mathbb R}$ has “nontrivial” degree if $\deg(f) < n$.)

1. Show that $f$’s real multilinear representation over $\{0,1\}$ (see Exercise 10), call it $q(x)$, also has $\deg(q) = k$.
2. Using Exercise 10(c),(d), deduce that $f$’s Fourier spectrum is “$2^{1-k}$-granular”, meaning each $\widehat{f}(S)$ is an integer multiple of $2^{1-k}$.
3. Show that $\sum_{S \subseteq [n]} |\widehat{f}(S)| \leq 2^{k-1}$.

1. Let’s index the rows and columns of $H_{2^n}$ by the integers $\{0, 1, 2, \dots, 2^n-1\}$ rather than $[2^n]$. Further, let’s identify such an integer $i$ with its binary expansion $(i_0, i_1, \dots, i_{n-1}) \in {\mathbb F}_2^n$, where $i_0$ is the least significant bit and $i_{n-1}$ the most. E.g., if $n = 3$, we identify the index $i = 6$ with $(0, 1, 1)$. Now show that the $(\gamma, x)$ entry of $H_{2^n}$ is $(-1)^{\gamma \cdot x}$.
2. Show that if $f : {\mathbb F}_2^n \to {\mathbb R}$ is represented as a column vector in ${\mathbb R}^{2^n}$ (according to the indexing scheme from part (a)) then $2^{-n} H_{2^n} f = \widehat{f}$. Here we think of $\widehat{f}$ as also being a function ${\mathbb F}_2^n \to {\mathbb R}$, identifying subsets $S \subseteq \{0, 1, \dots, n-1\}$ with their indicator vectors.
3. Show how to compute $H_{2^n} f$ using just $n 2^n$ additions and subtractions (rather than $2^{2n}$ additions and subtractions as the usual matrix-vector multiplication algorithm would require). This computation is called the Fast Walsh–Hadamard Transform and is the method of choice for computing the Fourier expansion of a generic function $f : {\mathbb F}_2^n \to {\mathbb R}$ when $n$ is large.
4. Show that taking the Fourier transform is essentially an “involution”: $\widehat{\widehat{f}} = 2^{-n} f$ (using the notations from part (b)).

1. Suppose $\mathbf{W}^{1}[f] = 1$. Show that $f(x) = \pm \chi_S$ for some $|S| = 1$.
2. Suppose $\mathbf{W}^{\leq 1}[f] = 1$. Show that $f$ depends on at most $1$ input coordinate.
3. Suppose $\mathbf{W}^{\leq 2}[f] = 1$. Must $f$ depend on at most $2$ input coordinates? At most $3$ input coordinates? What if we assume $\mathbf{W}^{2}[f] = 1$?

1. Generalize Exercise 6 as follows: Let $f : {\mathbb F}_2^n \to \{-1,1\}$ and suppose that $\mathrm{dist}(f, \chi_{S^*}) = \delta$. Show that $|\widehat{f}(S)| \leq 2\delta$ for all $S \neq S^*$. (Hint: use the union bound.)
2. Deduce that the BLR Test rejects $f$ with probability at least $3\delta – 10\delta^2 + 8\delta^3$.
3. Show that this lower bound cannot be improved to $c \delta – O(\delta^2)$ for any $c > 3$.

1. We call $f : {\mathbb F}_2^n \to {\mathbb F}_2$ an affine function if $f(x) = a \cdot x + b$ for some $a \in {\mathbb F}_2^n$, $b \in {\mathbb F}_2$. Show that $f$ is affine if and only if $f(x) + f(y) + f(z) = f(x+y+z)$ for all $x, y, z, \in {\mathbb F}_2^n$
2. Let $f : {\mathbb F}_2^n \to {\mathbb R}$. Suppose we choose ${\boldsymbol{x}}, \boldsymbol{y}, \boldsymbol{z} \sim {\mathbb F}_2^n$ independently and uniformly. Show that $\mathop{\bf E}[f({\boldsymbol{x}})f(\boldsymbol{y})f(\boldsymbol{z})f({\boldsymbol{x}}+\boldsymbol{y}+\boldsymbol{z})] = \sum_{S} \widehat{f}(S)^4$.
3. Give a $4$-query test for a function $f : {\mathbb F}_2^n \to {\mathbb F}_2$ with the following property: if the test accepts with probability $1-\epsilon$ then $f$ is $\epsilon$-close to being affine. All four query inputs should have the uniform distribution on ${\mathbb F}_2^n$ (but of course need not be independent).
4. Give an alternate $4$-query test for being affine in which three of the query inputs are uniformly distributed and the fourth is non-random. (Hint: show that $f$ is affine if and only if $f(x) + f(y) + f(0) = f(x+y)$ for all $x, y \in {\mathbb F}_2^n$.)

1. Show that $\widehat{f^{\pi}}(S) = \widehat{f}(\pi^{-1}(S))$ for all $S \subseteq [n]$.

For future reference, when we write $(\widehat{f}(S))_{|S|=k}$, we mean the sequence of degree-$k$ Fourier coefficients of $f$, listed in lexicographic order of the $k$-sets $S$.

Given complete truth tables of some $g$ and $h$ we might wish to determine whether they are isomorphic. One way to do this would be to define a canonical form $\text{can}(f) : \{-1,1\}^n \to \{-1,1\}$ for each $f : \{-1,1\}^n \to \{-1,1\}$, meaning that: (i) $\text{can}(f)$ is isomorphic to $f$; (ii) if $g$ is isomorphic to $h$ then $\text{can}(g) = \text{can}(h)$. Then we can determine whether $g$ is isomorphic to $h$ by checking whether $\text{can}(g) = \text{can}(h)$. Here is one possible way to define a canonical form for $f$:

• Set $P_0 = S_n$. 
• For each $k = 1, 2, 3, \dots, n$,
  • Define $P_k$ to be the set of all $\pi \in P_{k-1}$ which make the sequence $(\widehat{f^\pi}(S))_{|S|=k}$ maximal in lexicographic order on ${\mathbb R}^{\binom{n}{k}}$.
• Let $\text{can}(f) = f^{\pi}$ for (any) $\pi \in P_n$.

2. Show that this is well-defined, meaning that $\text{can}(f)$ is the same function for any choice of $\pi \in P_n$.
3. Show that $\text{can}(f)$ is indeed a canonical form; i.e., it satisfies (i) and (ii) above.
4. Show that if $\widehat{f}(\{1\}), \dots, \widehat{f}(\{n\})$ are distinct numbers then $\text{can}(f)$ can be computed in $\widetilde{O}(2^n)$ time.
5. We could more generally consider $g, h : \{-1,1\}^n \to \{-1,1\}$ to be isomorphic if $g(x) = h(\pm x_{\pi(1)}, \dots, \pm x_{\pi(n)})$ for some permutation $\pi$ on $[n]$ and some choice of signs. Extend the results of this exercise to handle this definition.