\documentclass[11pt]{article}
\usepackage{odonnell}
\begin{document}
\noindent {\large {\bf Analysis of Boolean Functions}} {\hfill {\bf CMU 18-859S / 21-801A, Fall 2012}}
\begin{center}
{\sc Problem Set 1} \\
{\bf Due: Monday, Sept.\ 17, beginning of class} \\
\end{center}
\hrule
\bigskip
\noindent {\bf Homework policy}: Please work on the homework by yourself; it isn't intended to be too difficult. Questions about the homework or other course material can be asked on Piazza.\\
\hrule
\bigskip
\begin{enumerate}
\item Compute the Fourier expansions of the following functions.
\begin{enumerate}
\item The \emph{selection function} $\SEL \co \bits^3 \to \{-1,1\}$ which outputs $x_2$ if $x_1 = -1$ and outputs~$x_3$ if $x_1 = 1$.
\item The indicator function $1_{\{a\}} \co \bn \to \{0,1\}$, where $a \in \bn$.
\item The density function corresponding to the product probability distribution on $\bn$ in which each coordinate has mean $\rho \in [-1,1]$;
\item The \emph{inner product mod $2$ function}, $\IP_{2n} \co \F_2^{2n} \to \{-1,1\}$ defined by $\IP_{2n}(x_1, \dots, x_n, y_1, \dots, y_n) = (-1)^{x \cdot y}$. (Here $x \cdot y$ denotes the dot-product in the vector space~$\F_2^n$.)
\item The \emph{hemi-icosahedron function} $\mathrm{HI} \co \bits^6 \to \bits$, 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$:
\myfig{.25}{hemi-icosahedron.pdf}{The hemi-icosahedron}{fig:hemi-icosahedron}
(Please give some indication of how you arrived at the expansion; a bare formula does not suffice.)
\end{enumerate}
\item Let $f \btb$. Let $\bx, \bx' \sim \bn$ be independent uniformly random strings and let $\mu = \E[f(\bx)]$. Show that
\begin{alignat*}{2}
\Var[f] &= \half \E[(f(\bx) - f(\bx'))^2] &&= 4\Pr[f(\bx) = 1]\Pr[f(\bx) = -1] \\ &= 2\Pr[f(\bx) \neq f(\bx')] &&= \E[|f(\bx) - \mu|].
\end{alignat*}
\item \label{ex:odd-even} The \emph{(boolean) dual} of $f \btR$ is the function $f^\booldual$ defined by $f^\booldual(x) = -f(-x)$. The function $f$ is said to be \emph{odd} if it equals its dual; equivalently, if $f(-x) = -f(x)$ for all $x$. The function~$f$ is said to be \emph{even} if $f(-x) = f(x)$ for all $x$. Given any function $f \btR$, its \emph{odd part} is the function $f^\odd \btR$ defined by $f^\odd(x) = (f(x) - f(-x))/2$, and its \emph{even part} is the function $f^\even \btR$ defined by $f^\even(x) = (f(x) + f(-x))/2$.
\begin{enumerate}
\item Express $\wh{f^\booldual}(S)$ in terms of $\wh{f}(S)$.
\item Verify that $f = f^\odd + f^\even$ and that $f$ is odd (respectively, even) if and only if $f = f^\odd$ (respectively, $f = f^\even$).
\item Show that
\begin{equation*}
f^\odd = \sum_{\substack{S \subseteq [n] \\ |S|\ \odd}} \wh{f}(S)\,\chi_S, \qquad f^\even = \sum_{\substack{S \subseteq [n] \\ |S|\ \even}} \wh{f}(S)\,\chi_S.
\end{equation*}
\end{enumerate}
\item Let $f \btb$.
\begin{enumerate}
\item Suppose $\W{1}[f] = 1$. Show that $f(x) = \pm \chi_S$ for some $|S| = 1$.
\item Suppose $\W{\leq 1}[f] = 1$. Show that $f$ depends on at most $1$ input coordinate.
\item Suppose $\W{\leq 2}[f] = 1$. Is it true that $f$ depends on at most $2$ input coordinates?
\end{enumerate}
\item A \emph{Hadamard matrix} is any $N \times N$ real matrix with $\pm 1$ entries and orthogonal rows. Particular examples are the \emph{Walsh--Hadamard matrices} $H_N$, inductively defined for $N = 2^n$ as follows: $H_1 = \begin{bmatrix} 1 \end{bmatrix}$, $H_{2^{n+1}} = \begin{bmatrix} H_{2^n} & H_{2^n} \\ H_{2^n} & -H_{2^n} \end{bmatrix}$.
\begin{enumerate}
\item 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 \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}$.
\item Show that if $f \ftR$ is represented as a column vector in $\R^{2^n}$ (according to the indexing scheme from part~(\emph{a})) then $2^{-n} H_{2^n} f = \wh{f}$. Here we think of $\wh{f}$ as also being a function $\F_2^n \to \R$, identifying subsets $S \subseteq \{0, 1, \dots, n-1\}$ with their indicator vectors.
\item Show that taking the Fourier transform is essentially an ``involution'': $\wh{\wh{f\, }} = 2^{-n} f$ (using the notations from part~(\emph{b})).
\item (Optional.) 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 \emph{Fast Walsh--Hadamard Transform}
and is the method of choice for computing the Fourier expansion of a generic function $f \ftR$ when $n$ is large.
\end{enumerate}
\item (Sanders '06.) Let $A \subseteq \F_2^n$, let $\alpha = |A|/2^n$, and write $1_A \co \F_2^n \to \{0,1\}$ for the indicator function of~$A$.
\begin{enumerate}
\item Show that $\sum_{S \neq \emptyset} \wh{1_A}(S)^2 = \alpha(1-\alpha)$.
\item Define $A + A + A = \{x + y + z : x, y, z \in A\}$, where the addition is in~$\F_2^n$. Show that either $A+A+A = \F_2^n$ or else there exists $S^* \neq \emptyset$ such that $|\wh{1_A}(S^*)| \geq \frac{\alpha}{1-\alpha} \cdot \alpha$. (Hint: if $A+A+A \neq \F_2^n$, show there exists~$x \in \F_2^n$ such that $1_A \ast 1_A \ast 1_A(x) = 0$.)
\end{enumerate}
\end{enumerate}
\end{document}