\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 6} \\
{\bf Due: Wednesday, Oct.\ 24, beginning of class} \\
\end{center}

\hrule

\bigskip

\noindent {\bf Homework policy}: Questions about the homework or other course material can be asked on Piazza.\\

\hrule

\bigskip

\begin{enumerate}
    \item Let $A \subseteq \bn$ have cardinality $\alpha 2^n$, $\alpha \leq 1/2$.  Thinking of $\bn \subset \R^n$, let $\mu_A \in \R^n$ be the center of mass of $A$.  Show that $\mu_A$ is close to the origin in Euclidean distance: $\|\mu_A\|_2 \leq O(\sqrt{\log(1/\alpha)})$.  (Hint: Level~$1$ Inequality.)
    \item (Chang's Lemma.) Let $A \subseteq \F_2^n$ have $|A|/2^n = \alpha \leq 1/2$. Let $\vphi_A$ denote the probability density function associated to the uniform distribution on~$A$.  Let $\eps > 0$ and let $\Gamma = \{ \gamma \in \F_2^n : |\wh{\vphi_A}(\gamma)| \geq \eps\}$.  (We use the notation from Homework~3, \#3.)
        \begin{enumerate}
            \item Compute $\E[\vphi_A^2]$ and use Parseval to show that $|\Gamma| \leq (1/\eps^2)(1/\alpha)$. (The goal of this exercise is to show that $\dim(\spn(\Gamma))$ is much smaller.)
            \item Let $\gamma_1, \dots, \gamma_d$ be a maximal set of linearly independent vectors in $\Gamma$.  Let $M \in \F_2^{n \times n}$ be an invertible matrix whose first~$d$ rows are $\gamma_1, \dots, \gamma_d$.  Let $A' = MA = \{M x : x \in A\}$ and let $\vphi_{A'}$ be the probability density function for the uniform distribution on~$A'$.  What can you say about $\wh{\vphi_{A'}}(0)$ and $\wh{\vphi_{A'}}(e_1), \dots, \wh{\vphi_{A'}}(e_d)$?  (Here $e_i = (0, \dots, 0, 1, 0, \dots, 0)$, with the~$1$ in the $i$th position.)
            \item Show that $d = \dim(\spn(\Gamma)) \leq O((1/\eps)^2 \log(1/\alpha))$.
        \end{enumerate}
    \item Let $\bX \not \equiv 0$ be a $B$-reasonable random variable; i.e., $\E[\bX^4] \leq B \E[\bX^2]^2$; i.e., $\|\bX\|_4 \leq B^{1/4} \|\bX\|_2$.
        \begin{enumerate}
            \item Show that $\Pr[|\bX| \geq t \|\bX\|_2] \leq B/t^4$ for all $t > 0$.  (Hint: apply Markov's Inequality to~$\bX^4$.)
            \item Let $\bY$ be a nonnegative random variable with $0 < \E[\bY^2] < \infty$.  Show the following ``second moment method'' inequality: $\Pr[\bY > \theta \E[\bY]] \geq (1-\theta)^2\frac{\E[\bY]^2}{\E[\bY^2]}$ for all $0 \leq \theta \leq 1$. (Hint: start by writing $\E[\bY] = \E[\bY \cdot \bone_{\{\bY \leq \theta \E[\bY]\}}] + \E[\bY \cdot \bone_{\{\bY > \theta \E[\bY]\}}]$; use Cauchy--Schwarz on the latter.)
            \item Show that $\Pr[|\bX| \geq t \|\bX\|_2] \geq (1-t^2)^2/B$ for all $0 \leq t \leq 1$.
        \end{enumerate}
    \item Let $\bx_1, \dots, \bx_n$ be independent uniform $\pm 1$ bits and let $a_1, \dots, a_n \in \R$.  Show that $a_1 \bx_1 + \cdots + a_n \bx_n$ is a $3$-reasonable random variable.
    \item Let $f \btR$.  Show that $\|\T_{1/\sqrt{3}} f\|_4 \leq \|f||_2$.  (Hint: show $\E[(\T_{1/\sqrt{3}} f(\bx))^4] \leq \E[f(\bx)^2]^2$ by induction on~$n$, similar to our proof of Bonami's Lemma.)
\end{enumerate}

\end{document}
