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

\begin{questions}
\question (O 3.29) Let $\phi: \F_2^n \rightarrow \R^{\geq 0}$ be a probability density function corresponding to probability
distribution $\Phi$ on $\F_2^n$.  Let $J \subseteq [n]$.
\begin{parts}
\part Consider the marginal probability distribution of $\Phi$ on coordinates J.
What is its probability density function (a function $\F_2^{J} \rightarrow \R^{\geq 0}$) in terms of $\phi$?

\begin{solution}

  \end{solution}

\part Consider the probability distribution of $\phi$ conditioned on a substring $s \in \F_2^{\overline{J}}$.
Assuming it’s well defined, what is its probability density function in terms of $\phi$?

\begin{solution}

  \end{solution}
\end{parts}

\question (O 3.16/3.38) Let $f: \{-1, 1\}^n \rightarrow \R$ and let $\eps > 0$. 
Show that $f$ is $\eps$-concentrated on a
collection $\mathcal{F} \subseteq 2^{[n]}$ with $|\mathcal{F}| \leq \hat{\|}f\hat{\|}_1^2/\eps$.

Let $\mathcal{C}$ be the set of functions $f$ such that $\hat{\|}f\hat{\|}_1 \leq s$.
Show that $\mathcal{C}$ can be learned with error $\eps$ in time $\poly(n, s, 1/\eps)$.
\begin{solution}

  \end{solution}

\question (O 3.44) Let $\tau \geq 1/2+\eps$ for some constant $\eps > 0$. 
Give an algorithm simpler than
Goldreich and Levin’s that solves the following problem with high probability:
Given query access to $f :\{-1, 1\}^n \rightarrow \{-1, 1\}$, in time $\text{poly}(n, 1/\eps)$ find
the unique $U \in [n]$ such that $|\widehat{f}(U)| \geq \tau$ assuming it exists. (Hint: First, consider the case $\eps = 1/2$.  Use the local correction algorithm from Lecture $2$ to generalize this.)
\begin{solution}

  \end{solution}


\question (O 3.45) Informally: a ``one-way permutation" is a bijective function $f: \F_2^{n} \rightarrow \F_2^n$
that is easy to compute on all inputs but hard to invert on more than a
negligible fraction of inputs; a ``pseudorandom generator" is a function $f: \F_2^{k} \rightarrow \F_2^m$ for $m > k$ whose output on a random input ``looks unpredictable" to any efficient algorithm. Goldreich and Levin proposed the following construction of the latter from the former: for $k = 2n, m= 2n+1$, define
\[
g(r, s) = (r, f(s), r \cdot s),
\]
where $r, s \in \F_2^n$ . When $g$’s input $(r, s)$ is uniformly random, then so is the first $2n$ bits of its output (using the fact that $f$ is a bijection). 
The key to the analysis is showing that the final bit, $r \cdot s$, is highly unpredictable to efficient algorithms even given the first $2n$ bits$ (r, f (s))$. 
This is proved by contradiction.
\begin{parts}
\part Suppose that an adversary has a deterministic, efficient algorithm $A$
good at predicting the bit $r \cdot s$:
\[
\Pr_{r, s \sim \F_2^n} \left[A(r, f(s)) = r \cdot s\right] \geq \frac{1}{2}+\gamma.
\]
Show there exists $B \subseteq \F_2^n$ with $|B|/2^n \geq \frac{1}{2}\gamma$ such that
\[
\Pr_{r \sim \F_2^n} \left[A(r, f(s)) = r \cdot s\right] \geq \frac{1}{2}+\frac{1}{2}\gamma.
\]
for all $s \in B$.
\begin{solution}

\end{solution}

\part Switching to $\pm 1$ notation in the output, deduce $\widehat{A_{| f(s)}}(s) \geq \gamma$ for all $s \in B$.
\begin{solution}

\end{solution}

\part Show that the adversary can efficiently compute s given $f(s)$ (with high probability) for any $s \in B$. 
If $\gamma$ is nonnegligible, this contradicts the assumption that $f$ is ``one-way". (Hint: Use the Goldreich–Levin
Algorithm.)
\begin{solution}

\end{solution}
\end{parts}

\end{questions}

\section*{Lecture 7}

\begin{questions}
\question (O 4.1) Show that every function $f: \{0,1\}^n \rightarrow \{0,1\}$ can be represented by a DNF formula of size at most $2^n$ and width at most $n$.
\begin{solution}

  \end{solution}

\question (O 4.3)  A DNF formula is said to be \emph{monotone} if its terms contain only unnegated variables. 
Show that monotone DNFs compute monotone functions and that any monotone function can be computed by a monotone DNF.
\begin{solution}

\end{solution}

\question (O 4.9) Give a direct (Fourier-free) proof of the following Corollary.
(Hint: Condition on whether $i \in J$.)

Fix $f: \{-1, 1\}^n \rightarrow \R$ and $i \in [n]$. 
If $(j | x)$ is a $\delta$-random restriction, then $\E[\text{Inf}_i[f_{J | x}]] = \delta \text{Inf}_i[f]$. Hence also $\E[\mathbf{I}[f_{J | x}]] = \delta \mathbf{I}[f]$.
\begin{solution}

\end{solution}

\question (Based on O 4.12) 
\begin{parts}
\part Show that the parity function $\chi_{[n]}: \{-1, 1\}^n \rightarrow \{-1, 1\}$ can be computed by a DNF (or a CNF) of size $2^{n-1}$.
\begin{solution}

\end{solution}

\part Show that the bound $2^{n-1}$ above is exactly tight. (Hint: Show that every term must have width exactly $n$.)
\begin{solution}

\end{solution}

\part Show that there is a depth-4 circuit of size $O(n^{1/2}2^{2n^{1/2}})$ computing $\chi_{[n]}$. (Hint: Break up the input into $n^{1/2}$ blocks of size $n^{1/2}$ and use (a) twice.)
\begin{solution}

\end{solution}

\part More generally, show there is a depth-$2d$ circuit of size $O(n^{1-1/d}2^{dn^{1/d}})$ computing $\chi_{[n]}$.
\begin{solution}

\end{solution}
\end{parts}

\end{questions}
\end{document}