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

\begin{questions}
\question (O 4.17) Let $f : \{\mathsf{True}, \mathsf{False}\}^n \rightarrow \{\mathsf{True}, \mathsf{False}\}$ be computable by a CNF $C$ of width $w$.
In this exercise you will show that $\mathbf{I}[f] \leq  w$.
Consider the following randomized algorithm that tries to produce an input $\mathbf{x} \in f^{-1}(\mathsf{True})$. 
First, choose a random permutation $\pi \in S_n$. 
Then for $1 = 1, \ldots, n$: If the single-literal clause $\mathbf{x}_{\pi(i)}$ appears in $C$, then set $\mathbf{x}_{\pi(i)} = \mathsf{True}$, syntactically simplify $C$ under this setting, and say that coordinate $\pi(i)$ is ``forced". 
Similarly, if the single-literal clause $\overline{\mathbf{x}}_{\pi(i)}$ appears in $C$, then set $\mathbf{x}_{\pi(i)} = \mathsf{False}$, syntactically simplify $C$, and say that $\pi(i)$ is ``forced".
If neither holds, set $\mathbf{x}_{\pi(i)}$ uniformly at random. 
If C ever contains two single-literal clauses $x_{j}$ and $\overline{x}_j$, the algorithm “gives up” and outputs $\mathbf{x} = \perp$
\begin{parts}
\part Show that if $\mathbf{x} \neq \perp$, then $f(\mathbf{x}) = \mathsf{True}$.

\begin{solution}

  \end{solution}

\part For $x \in f^{-1}(\mathsf{True})$ let $p(x)=  \Pr[\mathbf{x} = x]$. For $j \in [n]$ let $I_j$ be the indicator  random variable for the event that coordinate $j \in [n]$ is forced. 
Show that $p(x) = \E\left[\prod_{j=1}^n (1/2)^{1-I_j}\right]$

\begin{solution}

  \end{solution}

\part Deduce $2^n p(x) \geq 2 \sum_{j=1}^n \E[I_j]$

\begin{solution}

  \end{solution}

\part Show that for every $x$ with $f(x) = \mathsf{True}, f(x^{\oplus j}) = \mathsf{False}$ it holds that $\E[I_j \mid \mathbf{x} = x] \geq 1/w$

\begin{solution}

  \end{solution}

\part Deduce $\mathbf{I}[f] \leq w$.

\begin{solution}

  \end{solution}
\end{parts}

\question (O 4.19)In this exercise you will prove the Baby Switching Lemma with constant $3$ in place of $5$. 
Let $\phi = T_1 \vee T_2 \vee \cdots \vee T_s$ be a DNF of width $w \geq 1$ over variables $x_1, \ldots, x_n$. 
We may assume $\delta \leq 1/3$, else the theorem is trivial.

\begin{parts}
\part(a) Suppose $R = (J | z)$ is a ``bad" restriction, meaning that $\phi_{J| z}$ is not a constant function. 
Let $i$ be minimal such that $(T_i)_{J|z}$ is neither constantly True or False, and let $j$ be minimal such that $x_j$ or $\overline{x_j}$ appears in this restricted term. Show there is a unique restriction $R' = (J \backslash \{j\} | z')$ extending $R$ that doesn’t falsify $T_i$.
\begin{solution}

  \end{solution}

\part Suppose we enumerate all bad restrictions $R$, and for each we write the associated $R'$ as in (a). Show that no restriction is written more than $w$ times.
\begin{solution}

  \end{solution}

\part If $(J | z)$ is a $\delta$-random restriction and $R$ and $R'$ are as in (a), show that 
\[
\Pr[(J | z) = R] = \frac{2\delta}{1-\delta}\Pr[(J|z) = R']
\]
\begin{solution}

  \end{solution}

\part Complete the proof by showing $\Pr[(J | z) \text{ is bad}] \leq 3\delta w$
\begin{solution}

  \end{solution}
\end{parts}


\end{questions}

\section*{Lecture 9}

\begin{questions}
\question (O 5.2) Let $f(x) = \text{sgn}(a_0+a_1x_1+\cdots+a_nx_n)$ be an LTF.

\begin{parts}
\part Show that if $a_0 = 0$, then $\E[f] = 0$. (Hint: Show that f is in fact an odd function.)
\begin{solution}

  \end{solution}

\part Show that if $a_0 \geq 0$, then $\E[f] \geq 0$. Show that the converse need not hold.
\begin{solution}

  \end{solution}

\part Suppose $g : \{-1, 1\}^n \rightarrow \{-1, 1\}$ is an LTF with $\E[g] = 0$. Show that $g$ can be represented as $g(x) = \text{sgn}(c_1x_1+\cdots+c_nx_n)$
\begin{solution}

  \end{solution}
\end{parts}

\question (O 5.5)  Suppose $\ell: \{-1, 1\}^n \rightarrow \R$ is defined by $\ell(x) = a_0+a_1x_1+\cdots+a_nx_n$.
Define $\widetilde{\ell}: \{-1, 1\}^{n+1} \rightarrow \R$ is defined by $\widetilde{\ell}(x) = a_0x_0+a_1x_1+\cdots+a_nx_n$. 
Show that $\|\widetilde{\ell}\|_1 = \|\ell\|_1$ and $\|\widetilde{\ell}\|_2^2 = \|\ell\|_2^2$.
\begin{solution}

\end{solution}

\question (O 5.7) Consider the following ``correlation distillation" problem (cf. Exercise 2.56).
For each$i \in [n]$ there is a number $\rho_i \in [-1, 1]$ and an independent sequence
of pairs of $\rho_i$-correlated bits, $(a^{(1)}, b^{(1)}), (a^{(2)}, b^{(2)}), (a^{(3)}, b^{(3)})$, etc.
Party A on Earth has access to the stream of bits $a^{(1)}, a^{(2)}, a^{(3)}, \ldots$  and a party B on Venus has access to the stream $b^{(1)}, b^{(2)}, b^{(3)}, \ldots$.
 Neither party knows the numbers $\rho_1, \ldots, \rho_n$. 
The goal is for B to estimate these correlations. 
To assist in this, A can send a small number of bits to B. 
A reasonable strategy is for A to send $f(a^{(1)}), f(a^{(2)}), f(a^{(3)})$ to B, where $f: \{-1, 1\}^n \rightarrow \{-1, 1\}$ is some Boolean function. 
Using this information B can try to estimate $\E[f(a)b_i]$ for each $i$.
\begin{parts}
\part  Show that $\E[f(a)b_i] = \widehat{f}(i)\rho_i$.
\begin{solution}

  \end{solution}

\part This motivates choosing an $f$ for which all $\widehat{f}(i)$ are large. 
If we also insist all $\widehat{f}(i)$ be equal, show that majority functions f maximize this common value.
\begin{solution}

  \end{solution}
\end{parts}

\question (5.8)  For $n \geq 2$, let $f : \{-1, 1\}^n \rightarrow \{-1, 1\}$ be a randomly chosen function (as in Exercise 1.7). 
Show that $\hat{\|}f\hat{\|}_{\infty} \leq 2\sqrt{n}2^{-n/2}$ except with probability at most $2^{-n}$.

Hint: First, consider one Fourier coefficient.  Then apply a union bound.
\begin{solution}

\end{solution}

\end{questions}
\end{document}