\documentclass[11pt,addpoints,answers]{exam}

% Packages
\usepackage{fullpage}
\usepackage{latexsym,amssymb,amsfonts,amsmath,mathrsfs,float, amsthm}
\usepackage[font=small,labelfont=bf, width=.618\textwidth]{caption} % custom captions
\usepackage{xcolor}
\usepackage{tikz, graphics, enumerate}
\usepackage{hyperref}


% Paragraph indentation and spacing
\newcommand{\parset}{
	\setlength{\parskip}{3mm}
  	\setlength{\parindent}{0mm}}
	
% Probability
  \DeclareMathOperator{\var}{Var}
  \renewcommand{\Pr}{\mbox{\rm Pr}}	
  \newcommand{\Exp}{{\mathbb{E}}}
  \newcommand{\E}{\mathbb{E}}

% Sets 
  \newcommand{\R}{\mathbb{R}} % reals
  \newcommand{\C}{\mathbb{C}} % complex numbers
  \newcommand{\N}{\mathbb{N}} % natural numbers
  \newcommand{\Z}{\mathbb{Z}} % integers
  \newcommand{\F}{\mathbb{F}} % field
  \newcommand{\K}{\mathbb K} % field
  \newcommand{\T}{\mathbb T} % circle
\newcommand{\B}{\mathcal{B}} % ball
  \newcommand{\pmset}[1]{\{-1,1\}^{#1}} % hypercube in +-1 basis
  \newcommand{\bset}[1]{\{0,1\}^{#1}} % hypercube
  \newcommand{\sphere}[1]{S^{#1-1}} % real unit sphere of dimension #1
  \newcommand{\ball}[1]{B_{#1}} % real unit ball of dimension $1
  \newcommand{\Orth}[1]{O(\R^{#1})} % orthogonal group
  \DeclareMathOperator{\im}{im} % image
  \DeclareMathOperator{\vspan}{Span} % kernel
  \newcommand{\1}{\mathbf{1}}
  \DeclareMathOperator{\Cball}{\mathcal C}
  \DeclareMathOperator{\cay}{Cay} 
  \DeclareMathOperator{\sol}{Sol} 
\DeclareRobustCommand{\stirling}{\genfrac\{\}{0pt}{}}

% Miscellaneous
  \newcommand{\st}{:\,} % "such that" to define sets
  \newcommand{\ie}{{i.e.}}  
  \newcommand{\eg}{{e.g.}} 
  \newcommand{\eps}{\varepsilon}
  \newcommand{\ip}[1]{\langle #1 \rangle}
  \newcommand{\cF}{{\mathcal F}}   
  \DeclareMathOperator{\U}{\mathcal{U}}
  \DeclareMathOperator{\sign}{sign}
  \newcommand{\poly}{\mbox{\rm poly}}
  \newcommand{\ceil}[1]{\lceil{#1}\rceil}
  \newcommand{\floor}[1]{\lfloor{#1}\rfloor}
  \DeclareMathOperator{\Tr}{\mathsf{Tr}}
  \DeclareMathOperator{\diag}{diag}
  \DeclareMathOperator{\patt}{patt}
  \DeclareMathOperator{\argmin}{arg\,min}
  \DeclareMathOperator{\spec}{Spec}
  \DeclareMathOperator{\enc}{\sf Enc}
  \DeclareMathOperator{\dec}{\sf Dec}
  \DeclareMathOperator{\diam}{diam} 
  \DeclareMathOperator{\spn}{span} 
  \DeclareMathOperator{\geom}{gm}
\DeclareMathOperator{\sinc}{sinc}
\DeclareMathOperator{\disc}{disc}
\DeclareMathOperator*{\argmax}{arg\,max}
  \newcommand{\infnorm}{{\ell_\infty, \ldots, \ell_\infty}}
  \newcommand{\pnorm}{{\ell_p,\dots,\ell_p}}
  \newcommand{\tnorm}{{\ell_t,\dots,\ell_t}}
  
  
% Enviroments
  \newcommand{\beq}{\begin{equation}}
  \newcommand{\eeq}{\end{equation}}
  \newcommand{\beqn}{\begin{equation*}}
  \newcommand{\eeqn}{\end{equation*}}
  \newcommand{\beqr}{\begin{eqnarray}}
  \newcommand{\eeqr}{\end{eqnarray}}
  \newcommand{\beqrn}{\begin{eqnarray*}}
  \newcommand{\eeqrn}{\end{eqnarray*}}
  \newcommand{\bmline}{\begin{multline}}
  \newcommand{\emline}{\end{multline}}
  \newcommand{\bmlinen}{\begin{multline*}}
  \newcommand{\emlinen}{\end{multline*}}
  
  \makeatletter

% END OF SUPPLIED VARIABLES

  \chead{\large \textbf{Week 2 Questions}}

  \lhead{\small
    \textbf{{Boolean Functions}\\{Northwestern \\Winter 2021}}}

  \rhead{\small \textbf{Instructor:
     {Shravas Rao}}\\\textbf{Student}: FIRSTNAME LASTNAME}

  \setlength{\headheight}{20pt}
  \setlength{\headsep}{16pt}                       
  \headrule
% execute homework commands

\begin{document}

\pagestyle{head}                % put header on every page

\medskip

\section*{Lecture 2}

\begin{questions}
\question (O 1.23) In this exercise, you will prove some basic facts about ``distances" between probability distributions.  Let $\phi$ and $\psi$ be probability densities on $\F_2^n$.

Recall that
\[
\|f\|_p = \E[|f(x)|^p]^{1/p}
\]
and that Jensen's inequality states that if $0 < p < q$, then
\[
\E[|f(x)|^p]^{1/p} \leq \E[|f(x)|^q]^{1/q}.
\]

\begin{parts}
\part Show that the \emph{total variation distance} between $\phi$ and $\psi$, defined by
\[
d_{\text{TV}}(\phi, \psi) = \max_{A \subseteq \F_2^n} \left\{\left|\Pr_{y \sim \phi}[y \in A] - \Pr_{y \sim \psi}[y \in A] \right|\right\}
\]
is equal to $\frac{1}{2}\|\phi-\psi\|_1$.

\begin{solution}

  \end{solution}

\part Show that the \emph{collision probability} of $\phi$, defined to be
\[
\Pr_{\substack{y, y' \sim \phi \\\text{independently}}}[y = y']
\]
is equal to $\|\phi\|_2^2/2^n$.
\begin{solution}

  \end{solution}

\part The $\chi^2$-\emph{distance of $\phi$ from $\psi$} is defined by
\[
d_{\chi^2}(\phi, \psi) = \E_{y \sim \psi} \left[\left(\frac{\phi(y)}{\psi(y)}-1\right)^2\right],
\]
assuming $\psi$ has full support.
Show that the $\chi2$-distance of $\phi$ from uniform is equal to $\var[\phi]$.
\begin{solution}

  \end{solution}

\part Show that the total variation distance of $\phi$ from uniform is at most $\frac{1}{2}\sqrt{\var[\phi]}$.
\begin{solution}

  \end{solution}
\end{parts}

\question Let $f: \F_2^n \rightarrow \R$.  Construct functions $g_1, g_2 : \F_2^n \rightarrow \R$ such that

\begin{parts}
\part $f * g_1 = D_i f$ where $D_i f(x) = (f(x)-f(x^{\oplus i}))/2$
\begin{solution}

\end{solution}

\part $f * g_2 = T_{\rho} f$ where $T_{\rho} f = \sum_{S \subset [n]} \rho^{|S|} \widehat{f}(S) \chi_S$.
\begin{solution}

\end{solution}
\end{parts}

\question (O 1.29)

\begin{parts}
\part We call $f: \F_2^n \rightarrow \F_2$ an \emph{affine} function if $f(x) = a \cdot x+b$ for some $a \in \F_2^n, b \in \F_2$.
Show that $f$ is affine if and only if $f(x)+f(y)+f(x) = f(x+y+z)$ for all $x, y, z \in \F_2^n$.
\begin{solution}

\end{solution}

\part Let $f: \F_2^n \rightarrow \R$.  Suppose we choose $x, y, z \sim \F_2^n$ independently and uniformly.  Show that $\E[f(x)f(y)f(z)f(x+y+z)] = \sum_{S} \hat{f}(S)^4$.
\begin{solution}

\end{solution}	

\part Give a $4$-query test for a function $f: \F_2^n \rightarrow \F_2$ with the following property.
If the test accepts with probability $1-\eps$ then $f$ is $\eps$-close to being affine.
All four query inputs should have the uniform distribution on $\F_2^n$ (but of course need not be independent).
\begin{solution}

\end{solution}	

\part Give an alternate $4$-query test for being affine in which three of the query inputs are uniformly distributed and the fourth is not random.
(Hint: Show that $f$ is affine if and only if $f(x)+f(y)+f(0) = f(x+y)$ for all $x, y \in \F_2^n$.)
\begin{solution}

\end{solution}
\end{parts}
\end{questions}

\section*{Lecture 3}

\begin{questions}
\question (O 2.3) Prove \emph{May's Theorem}:

\begin{parts}
\part Show that $f: \{-1, 1\}^n \rightarrow \{-1, 1\}$ is symmetric and monotone if and only if it can be expressed as a weighted majority with $a_1 = a_2 = \cdots = a_n = 1$. (That is, $f(x) = \sign(a_0+x_1+x_2+\cdots+x_n)$ for some $a_0$)

\begin{solution}

  \end{solution}

\part Suppose $f: \{-1, 1\}^n \rightarrow \{-1, 1\}$ is symmetric, monotone, and odd.  Show that $n$ must be odd, and that $f = \text{Maj}_n$.
\begin{solution}

  \end{solution}
\end{parts}

\question (O 2.19) Suppose $f, g: \{-1, 1\}^n \rightarrow \R$ have the property that $f$ does not depend on the $i$th coordinate and $g$ does not depend on the $j$th coordinate ($i \neq j$).
Show that $\E[x_ix_jf(x)g(x)] = \E[D_jf(x)D_ig(x)]$.

Here, $D_i f(x) = \frac{f(x^{i \mapsto 1})-f(x^{i \mapsto -1})}{2}$.
\begin{solution}

\end{solution}

\question (Based on O 2.15) Define $E_if(x) = \frac{f(x^{i \mapsto 1})+f(x^{i \mapsto -1})}{2}$.
Prove that $f = x_iD_if+E_if$, and give the Fourier coefficients of $E_i f$ in terms of the Fourier coefficients of $f$.
\begin{solution}

\end{solution}

\question (Based on O 2.27) Which functions $f: \{-1, 1\}^n \rightarrow \{0, 1\}$ such that $|\{x \st f(x) = 1\}| = 3$ maximize $\mathbf{I}[f]$?
\begin{solution}

\end{solution}

\end{questions}
\end{document}