\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 2} \\
{\bf Due: Monday, Sept.\ 24, beginning of class} \\
{\bf Turn in problems \#1--\#4, plus either \#5 or \#6} \\
\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 Here are some more linear operators on the vector space of functions $f \co \bn \to \R$:
\begin{itemize}
\item The \emph{$i$th expectation operator} $\uE_i$, defined by $\displaystyle \uE_if (x) = \frac{f(x^{(i \mapsto +1)}) + f(x^{(i \mapsto -1)})}{2}$.
\item The \emph{$i$th directional Laplacian operator} $\Lap_i$, defined by $\displaystyle \Lap_if = f - \uE_i f$.
\item The \emph{Laplacian operator} $\Lap$, defined by $\displaystyle \Lap f = \Lap_1 f + \Lap_2 f + \cdots + \Lap_n f$.
\end{itemize}
Prove the following formulas:
\begin{enumerate}
\item $\displaystyle \uE_i f(x) = \sum_{S \not \ni i} \wh{f}(S) x^S$.
\item $f(x) = \uE_if(x) + x_i \D_i f(x)$.
\item $\displaystyle \Lap_if (x) = \frac{f(x) - f(x^{\oplus i})}{2} = \sum_{S \ni i} \wh{f}(S)x^S$.
\item $\la f, \Lap_i f \ra = \la \Lap_i f, \Lap_i f \ra = \Inf_i[f]$.
\item $\displaystyle \Lap f(x) = (n/2)\bigl(f(x) - \avg_{i \in [n]} f(x^{\oplus i})\bigr) = \sum_{S \subseteq [n]} |S| \wh{f}(S) x^S$.
\item $\la f, \Lap f \ra = \Tinf[f]$.
\end{enumerate}
\item In 1965, the Nassau County (New York) Board used a weighted majority voting system to make its decisions, with the $6$ towns getting differing weights based on their population. Specifically, the board used the voting rule $f \co \zo^6 \to \bits$ defined by $f(x) = \sgn(-58 + 31x_1 + 31x_2 + 28x_3 + 21x_4 + 2x_5 + 2x_6)$. Compute $\Inf_i[f]$ for all $i \in [6]$. (PS: John Banzhaf invented the notion of $\Inf_i$ while suing on behalf of towns \#5 and \#6.)
\item Let $f \btb$ be unbiased (i.e., $\E[f] = 0$), and let
$\MaxInf[f]$ denote $\max_{i \in [n]}\{\Inf_i[f]\}$. Recall that the KKL~Theorem implies $\MaxInf[f] \geq \Omega(\frac{\log n}{n})$. In 1987, this was still a conjecture; all that was known was the following results, independently observed by Alon and by Chor and Ger\'{e}b-Graus\dots
\begin{enumerate}
\item Use the Poincar\'{e} Inequality to show $\MaxInf[f] \geq 1/n$.
\item Prove $|\wh{f}(i)| \leq \Inf_i[f]$ for all $i \in [n]$. (Hint: consider $\E[|\D_i f|]$.)
\item Prove that $\Tinf[f] \geq 2 - n \MaxInf[f]^2$. (Hint: first prove $\Tinf[f] \geq \W{1}[f] + 2(1-\W{1}[f])$ and then use the previous exercise.)
\item Deduce that $\MaxInf[f] \geq \frac{2}{n} - \frac{4}{n^2}$.
\end{enumerate}
(Later in 1987, Chor and Ger\'{e}b-Graus managed to improve the lower bound to $\frac{3}{n} - o(1/n)$.)
\item (Remark: this is really a problem in combinatorics, not Fourier analysis.)
The \emph{polarizations} of~$f \btR$ (also known as
compressions, downshifts, or two-point rearrangements) are defined as follows. For $i \in [n]$, the $i$-polarization of $f$ is the function $f^{\sigma_i} \btR$ defined by
\[
f^{\sigma_i}(x) = \begin{cases}
\max\{f(x^{(i \mapsto +1)}), f(x^{(i \mapsto -1)})\} & \text{if $x_i = +1$,} \\
\mathrlap{\min}\phantom{\max}\{f(x^{(i \mapsto +1)}), f(x^{(i \mapsto -1)})\} & \text{if $x_i = -1$.}
\end{cases}
\]
\begin{enumerate}
\item Show that $\E[f^{\sigma_i}] = \E[f]$.
\item Show that $\Inf_{j}[f^{\sigma_i}] \leq \Inf_{j}[f]$ for all $j \in [n]$.
\item (Optional.) Show that $\Stab_\rho[f^{\sigma_i}] \geq \Stab_\rho[f]$ for all $0 \leq \rho \leq 1$.
\item Show that $f^{\sigma_i}$ is monotone in the~$i$th direction. (We say $g$ is ``monotone in the $i$th direction'' if $g(x^{(i \mapsto +1)}) \geq g(x^{(i \mapsto -1)})$ for all~$x$.) Further, show that if $f$ is monotone in the $j$th direction for some $j \in [n]$ then $f^{\sigma_i}$ is still monotone in the $j$th direction.
\item Let $f^* = f^{\sigma_1 \sigma_2 \cdots \sigma_n}$. Show that $f^*$ is monotone, $\E[f^*] = \E[f]$, $\Inf_j[f^*] \leq \Inf_j[f]$ for all $j \in [n]$, and $\Stab_\rho[f^*] \geq \Stab_\rho[f]$ for all $0 \leq \rho \leq 1$ (you may use part~(c)).
\end{enumerate}
\item (Enflo, 1970.) The Hamming distance $\hamdist(x,y) = \#\{i : x_i \neq y_i\}$ on the discrete cube $\bits^n$ is an example of an \emph{$\ell_1$ metric space}. For $D \geq 1$, we say that the discrete cube can be \emph{embedded into $\ell_2$ with distortion~$D$} if there is a mapping $F \co \bn \to \R^m$ for some $m \in \N$ such that:
\begin{align*}
\|F(x) - F(y)\|_2 &\geq \hamdist(x,y) \text{ for all $x$, $y$;} \tag{``no contraction''}\\
\|F(x) - F(y)\|_2 &\leq D \cdot \hamdist(x,y) \text{ for all $x$, $y$.} \tag{``expansion at most $D$''}
\end{align*}
In this problem you will show that the least distortion possible is $D = \sqrt{n}$.
\begin{enumerate}
\item Recalling the definition of $f^\odd$ from Homework~1, show that for any $f \btR$ we have $\|f^\odd\|_2^2 \leq \Tinf[f]$ and hence
\[
\Ex_{\bx}[(f(\bx) - f(-\bx))^2] \leq \sum_{i = 1}^n \Ex_{\bx}\Bigl[\bigl(f(\bx) - f(\bx^{\oplus i})\bigr)^2\Bigr].
\]
\item Suppose $F \co \bn \to \R^m$, and write $F(x) = (f_1(x), f_2(x), \dots, f_m(x))$ for functions $f_i \co \bn \to \R$. By summing the above inequality over $i \in [m]$, show that any $F$ with no contraction must have expansion at least $\sqrt{n}$.
\item Show that there is an embedding $F$ achieving distortion $\sqrt{n}$.
\end{enumerate}
\item (Lata{\l}a--Oleszkiewicz, 1994.) Let $V$ be a vector space with norm $\| \cdot \|$ and fix $w_1, \dots, w_n \in V$. Define $g \btR$ by $g(x) = \|\sum_{i=1}^n x_i w_i\|$.
\begin{enumerate}
\item Recalling the operator $\Lap$ from Problem~1, show that $\Lap g \leq g$ pointwise. (Hint: triangle inequality.)
\item Deduce $2\Var[g] \leq \E[g^2]$ and thus the
\emph{Khintchine--Kahane inequality}:
\[
\E_{\bx}\left[\left\|\littlesum_{i=1}^n \bx_i w_i\right\|\right] \geq \frac{1}{\sqrt{2}} \cdot \E_{\bx}\left[\left\|\littlesum_{i=1}^n \bx_i w_i\right\|^2\right]^{1/2}.
\]
(Hint: first, show that the improved Poincar\'{e} inequality $\Var[f] \leq \half \Tinf[f]$ holds whenever $f \btR$ is even, as defined in Homework~1.)
\item Show that the constant $\frac{1}{\sqrt{2}}$ above is optimal (Hint: take $V = \R$ and $n = 2$.)
\end{enumerate}
\end{enumerate}
\end{document}