\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}



