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

\begin{questions}
\question (O 2.31) Show that $T_{\rho}$ is \emph{positivity-preserving} for $\rho \in [-1, 1]$; i.e., $f \geq 0$ implies $T_{\rho}f \geq 0$.
Show that $T_{\rho}$ is \emph{positivity-improving} for $\rho \in (-1, 1)$; i.e., $f \geq 0$ and $f \neq 0$ implies $T_{\rho}f > 0$.

\begin{solution}

  \end{solution}

\question (O 2.34) Show that $|T_{\rho}f| \leq T_{\rho}|f|$ pointwise for any $f: \{-1, 1\}^n \rightarrow \R$.
Further show that for $\rho \in (-1, 1)$, equality occurs if and only if $f$ is everywhere nonnegative or everywhere nonpositive.
\begin{solution}

  \end{solution}

\question (O 2.36) Show that $\text{Stab}_{-\rho}[f] = -\text{Stab}_{\rho}[f]$ if $f$ is odd and $\text{Stab}_{-\rho}[f] = \text{Stab}_{\rho}[f]$ if $f$ is even.
\begin{solution}

  \end{solution}


\question (O 2.53) The Hamming distance $\Delta(x, y) = |\{i\st x_i \neq y_i\}|$ on the discrete cube $\{-1, 1\}^n$ is an example of an $\ell_1$ \emph{metric space}.
For $D \geq 1$, we say that the discrete cube can be embedded into $\ell_2$ with distortion $D$ if there is a mapping $F: \{-1, 1\}^n \rightarrow \R^m$ for some $m \in \mathbb{N}$ such that:
\begin{itemize}
\item $\|F(x)-F(y)\|_2 \geq \Delta(x, y) \text{ for all x, y}$ (no contraction)
\item $\|F(x)-F(y)\|_2 \leq D \Delta(x, y) \text{ for all x, y}$ (expansion at monst $D$)
\end{itemize}
In this exercise you will show that the least distortion possible is $D = \sqrt{n}$.

\begin{parts}
\part Recalling the definition of $f^{\text{odd}}$ from Exercise 1.8, show that for any $f: \{-1, 1\}^n \rightarrow \R$ we have $\|f^{\text{odd}}\|_2^2 \leq \mathbf{I}[f]$ and hence
\[
\E_x[(f(x)-f(-x))^2] \leq \sum_{i=1}^n \E_x\left[\left(f(x)-f(x^{\oplus i})\right)^2\right].
\]
\begin{solution}

\end{solution}

\part Suppose $F: \{-1, 1\}^n \rightarrow \R^m$ and write $F(x) = (f_1(x), f_2(x), \ldots, f_m(x))$ for functions $f_i: \{-1, 1\}^n \rightarrow \R$.
By summing the above inequality over $i \in [m]$, show that any $F$ with no contraction must have expansion at least $\sqrt{n}$.
\begin{solution}

\end{solution}

\part Show that there is an embedding $F$ achieving distortion $\sqrt{n}$.
\begin{solution}

\end{solution}
\end{parts}

\end{questions}

\section*{Lecture 5}

\begin{questions}
\question (O 3.4) Prove Lemma 3.5 (listed below) by induction on $n$.  (Hint: If one of the subfunctions $f(x_1, x_2, \ldots, x_n, \pm1)$ is identically $0$, show that the other has degree at most $k-1$.)

Suppose $\deg(f) \leq k$ where $f: \{-1, 1\}^n \rightarrow \R$ is not identically $0$.
Then $\Pr[f(x) \neq 0 \geq 2^{-k}]$.
\begin{solution}

  \end{solution}

\question (O 3.15) Given $f: \F_2^n \rightarrow \R$, define its \emph{fractional sparsity} to be $\text{sparsity}(f) = |\text{supp}(f)|/2^n = \Pr_{x \in \F_2^n} [f(x) \neq 0]$.
In this exercise, you will prove the \emph{uncertainty princple}: If $f$ is non-zero, then $\text{sparsity}(f) \cdot \text{sparsity}(\widehat{f}) \geq 1:$

\begin{parts}
\part Show that we may assume $\|f\|_1= 1$.
\begin{solution}

\end{solution}

\part Suppose $\mathcal{F} = \{\gamma \st \widehat{f}(\gamma) \neq 0\}$.  Show that $\hat{\|} f \hat{\|}_2^2 \leq |\mathcal{F}|$.
\begin{solution}

\end{solution}

\part Suppose $\mathcal{G} = \{x \st f(x) \neq 0\}$.  Show that $\|f\|_2^2 \geq 2^{n}/|\mathcal{G}|$.

Hint: Recall that Cauchy-Schwarz says that $\langle f, g\rangle \leq \|f\|_2\|g\|_2$.
\begin{solution}

\end{solution}

\part Identify all cases of equality.
\begin{solution}

\end{solution}
\end{parts}

\question (O 3.19) Let $f: \F_2^n \rightarrow \R$ be computable by a decision tree of size $s$ and depth $k$
Show that $-f$ and the Boolean dual $f^{\dagger}$ are also computable by decision trees of size $s$ and depth $k$.
\begin{solution}

\end{solution}

\question (O 3.34) Improve Proposition 3.31 as follows.  Suppose $f: \{-1, 1\}^n \rightarrow \{-1, 1\}$ and $g: \{-1, 1\}^n \rightarrow \R$ satisfy $\|f-g\|_1 \leq \eps$.
Pick $\theta \in [-1, 1]$ uniformly at random and define $h: \{-1, 1\}^n \rightarrow \{-1, 1\}$ by $h(x) = \text{sgn}(g(x)-\theta)$.
Show that $\E[\text{dist}(f, h)] \leq \eps/2$.
\begin{solution}

\end{solution}

\end{questions}
\end{document}