\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 5} \\
{\bf Due: Monday, Oct.\ 15, beginning of class} \\
\end{center}
\hrule
\bigskip
\noindent {\bf Homework policy}: Please try to 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 Suppose $f(x) = \sgn(a_0 + a_1 x_1 + \cdots a_n x_n)$ is an LTF with $|a_1| \geq |a_2| \geq \cdots \geq |a_n|$. Show that $\Inf_1[f] \geq \Inf_2[f] \geq \cdots \geq \Inf_n[f]$.
\item \label{ex:FKN-0-and-1} In class we will discuss the FKN~Theorem and the proof of the following: If $f \btb$ has $\E[f] = 0$ and $\W{1}[f] \geq 1-\delta$ then $f$ is $O(\delta)$-close to $\pm \chi_i$ for some $i \in [n]$. \emph{Assuming this}, show the following: If $f \btb$ has $\W{\leq 1}[f] \geq 1-\delta$ then $f$ is $O(\delta)$-close to a $1$-junta. (Hint: define $g(x_0, x) = x_0 f(x_0 x)$.)
\item \begin{enumerate}
\item Suppose $\ell \btR$ is defined by $\ell(x) = a_0 + a_1 x_1 + \cdots a_n x_n$. Define $\wt{\ell} \co \bits^{n+1} \to \R$ by $\wt{\ell}(x_0, \dots, x_n) = a_0 x_0 + a_1 x_1 + \cdots a_n x_n$. Show that $\|\wt{\ell}\|_1 = \|\ell\|_1$ and $\|\wt{\ell}\|^2_2 = \|\ell\|_2^2$.
\item Show that if $f = \sgn(\ell)$ is any LTF then $\W{\leq 1}[f] \geq 1/2$. (Recall that we proved this in class assuming $a_0 = 0$ using Homework \#2, Problem \#6.)
\end{enumerate}
\item Consider the sequence of LTFs $f_n \co \bits^n \to \{0,1\}$ defined by $f_n(x) = 1$ if and only if $\sum_{i=1}^n \tfrac{1}{\sqrt{n}} x_i > t$. (I.e., $f_n$ is the indicator of the Hamming ball of radius $\frac{n}{2} - \frac{t}{2}\sqrt{n}$ centered at $(1, 1, \dots, 1)$.) Show that
\[
\lim_{n \to \infty} \E[f_n] = \overline{\Phi}(t), \qquad \lim_{n \to \infty} \W{1}[f_n] = \phi(t)^2,
\]
where $\phi$ is the pdf of a standard Gaussian and $\overline{\Phi}$ is the complementary cdf (i.e., $\overline{\Phi}(u) = \int_{u}^\infty \phi$). You may use the Central Limit Theorem without worrying about error bounds.
\item For integer $0 \leq k \leq n$, define $\mathscr{K}_k \btR$ by $\mathscr{K}_k(x) = \sum_{|S| = k} x^S$. Since $\mathscr{K}_k$ is symmetric, the value $\mathscr{K}_k(x)$ depends only on the number~$z$ of $-1$'s in~$x$; or equivalently, on $\sum_{i=1}^n x_i$. Thus we may define $\mathscr{K}_k \co \{0, 1, \dots, n\} \to \R$ by $\mathscr{K}_k(z) = \mathscr{K}_k(x)$ for any $x$ with $\sum_i x_i = n - 2z$.
\begin{enumerate}
\item Show that $\mathscr{K}_k(z)$ can be expressed as a degree-$k$ polynomial in~$z$. It is called the \emph{Kravchuk (\emph{or} Krawtchouk) polynomial} of degree~$k$.
(The dependence on~$n$ is usually implicit.)
\item Show that $\sum_{k=0}^n \mathscr{K}_k(x) = \begin{cases} 2^n &\text{if $x = (1, \dots, 1)$,} \\ 0 & \text{else.}\end{cases}$.
\item Show for $\rho \in [-1,1]$ that $\sum_{k=0}^n \mathscr{K}_k(x)\rho^k = 2^n\Pr[\by = (1, \dots, 1)]$, where~$\by = N_\rho(x)$.
\item Deduce the following generating function identity: $\mathscr{K}s_k(z) = [\rho^k]((1-\rho)^z(1+\rho)^{n-z})$; i.e., the coefficient on $\rho^k$ in $(1-\rho)^z(1+\rho)^{n-z}$.
\end{enumerate}
\item Say that $\vec{\bZ}, \vec{\bZ'}$ are ``$\rho$-correlated $d$-dimensional Gaussians'' if the pairs $(\vec{\bZ}_1, \vec{\bZ'}_1), \dots, (\vec{\bZ}_d, \vec{\bZ'}_d)$ are independent $\rho$-correlated Gaussians. Now given $f \co \R^d \to \bits$ and $\eps \in \R$, define the \emph{rotation sensitivity} of $f$ at $\eps$ to be
\[
\mathbf{RS}_f(\eps) = \Pr[f(\vec{\bZ}) \neq f(\vec{\bZ'})],
\]
where $\vec{\bZ}$ and $\vec{\bZ'}$ are $\cos(\eps)$-correlated $d$-dimensional Gaussians.
\begin{enumerate}
\item Show that $\mathbf{RS}_f(0) = 0$, $\mathbf{RS}_{f}(\pi/2) = \half$ if $\Pr[f(\vec{\bZ}) = 1] = \half$, and $\mathbf{RS}_f(\pi) = 1$ if $f$ is an odd function (meaning $f(-x) = -f(x)$).
\item For $j = 0, 1, \dots, \ell$, let $\vec{u}_j$ be the unit vector in $\R^2$ making an angle of $j \eps$ with the $x$-axis. Let~$\vec{\bY}$ be a standard $2$-dimensional Gaussian and define $\bZ_j = \la \vec{u}_j, \vec{\bY} \ra$. Show that $\bZ_j$ and~$\bZ_{j+k}$ are $\cos(k\eps)$-correlated standard Gaussians.
\item Describe how to generate a sequence of $d$-dimensional Gaussians $\vec{\bZ}^{(0)}, \dots, \vec{\bZ}^{(\ell)}$ such that each pair $\vec{\bZ}^{(j)}, \vec{\bZ}^{(j+k)}$ is $\cos(k\eps)$-correlated (as defined in the first sentence of this problem).
\item Show that for any $f \co \R^d \to \bits$, $\eps \in \R$, and $\ell \in \N^+$ we have $\mathbf{RS}_f(\ell \eps) \leq \ell \mathbf{RS}_f(\eps)$. (Hint: previous part + union bound.)
\item Let $f \co \R^d \to \bits$ satisfy $\Pr[f(\vec{\bZ}) = 1] = 1/2$ where $\vec{\bZ}$ is a $d$-dimensional Gaussian. Let $\eps = \frac{\pi}{2\ell}$ for some $\ell \in \N^+$. Show that $\mathbf{RS}_f(\eps) \geq \eps/\pi$. (This last result is a special case of a 1985 theorem of Borell and is also generalization of a special case of the Gaussian Isoperimetric Inequality\dots)
\end{enumerate}
\item (Bonus problem due to [JOW'12].) Let $\bX$ and $\bY$ be symmetric random variables (meaning $-\bX$ has the same distribution as~$\bX$, and similarly for $\bY$). Show that $\min\{\Var[\bX], \Var[\bY]\} \leq C \cdot \Var[|\bX+\bY|]$ for some universal constant~$C$.
\end{enumerate}
\end{document}