\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 9 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 16}

\begin{questions}
\question (O 7.24) 
This problem is similar to Exercise 7.23 in that it shows you may assume that Dictator-vs.-No-Notables tests are testing ``smoothed" functions of the form $T_{1-\delta} h$ for $h: \{-1, 1\}^n \rightarrow [-1, 1]$, so long as you are willing to lose $O(\delta)$ in the probability that dictators are accepted.
\begin{parts}
\part Let $U$ be an $(\alpha, \beta)$-Dictator-vs.-No-Notables test using an arity-$r$ predicate set $\Psi$ (over domain $\{-1, 1\}$) which works under the assumption that the function $f:\{-1, 1\}^n \rightarrow [-1, 1]$  being tested is of the form $T_{1-\delta} h$ for $h: \{-1, 1\}^n \rightarrow [-1, 1]$. 
Modify $U$ as follows: whenever it is about to query $f(x)$, let it draw $y \sim N_{1-\delta}(x)$ and use $f(y)$ instead. 
Call the modified test $U'$. 
Show that the probability $U'$ accepts an arbitrary $h: \{-1, 1\}^n \rightarrow [-1, 1]$ is equal to the probability $U$ accepts $T_{1-\delta} h$.

\begin{solution}

  \end{solution}

\part Prove that $U'$ is an $(\alpha, \beta-r\delta/2)$-Dictator-vs.-No-Notables test using predicate set $\Psi$.
\begin{solution}

  \end{solution}
\end{parts}

\question (O 7.26) Show that when using Theorem 7.40, it suffices to have a ``Dictators-vs.-No-Influentials test", meaning replacing $\text{Inf}_i^{(1-\eps)}[f]$ in Definition 7.37 with just $\text{Inf}_i[f]$. (Hint: Exercise 7.24.)

\begin{solution}

  \end{solution}

\question (O 7.28)  In this problem you will show that Corollary 7.43 actually follows directly from Corollary 7.44.

\begin{parts}
\part Consider the $\F_2$-linear equation $v_1+v_2+v_3 = 0$. 
Exhibit a list of $4$ clauses (i.e., logical ORs of literals) over the variables such that if the equation is satisfied, then so are all $4$ clauses, but if the equation is not satisfied, then at most $3$ of the clauses are. 
Do the same for the equation $v_1+v_2+v_3 = 1$

\begin{solution}

  \end{solution}

\part Suppose that for every $\delta > 0$ there is an efficient algorithm for $(\frac{7}{8}+\delta, 1-\delta)$-approximating Max-E3-Sat. 
Give, for every $\delta > 0$, an efficient algorithm for $(\frac{1}{2}+\delta, 1-\delta)$-approximating Max-E3-Lin.
\begin{solution}

  \end{solution}

\part Alternatively, show how to transform any $(\alpha, \beta)$-Dictator-vs.-No-Notables test using Max-E3-Lin predicates into a $(\frac{3}{4}+\frac{1}{4}\alpha, \beta)$-Dictator-vs.-No-Notables test using Max-E3-Sat predicates.
\begin{solution}

  \end{solution}
\end{parts}

\end{questions}

\section*{Lecture 18}

\begin{questions}
\question (O 9.8) Fix $k  \in N$. 
The goal of this exercise is to show that ``projection to degree $k$ is a bounded operator in all $L_p$ norms, $p > 1$". 
Let $f: \{-1, 1\}^n \rightarrow \R$.
\begin{parts} 
\part Let $q \geq 2$. 
Show that $\|f ^{\leq k}\|_q \leq \sqrt{q-1}^k \|f\|_q$.
(Hint: Use Theorem 9.21 to show the stronger statement $\|f ^{\leq k}\|_q \leq \sqrt{q-1}^k \|f\|_2$.)
\begin{solution}

\end{solution}

\part Let $1 <  q \leq 2$. 
Show that $\|f ^{\leq k}\|_q \leq (1/\sqrt{q-1})^k \|f\|_q$. 
(Hint: Either give a similar direct proof using the $(p,2)$-Hypercontractivity Theorem, or explain how this follows from part (a) using the dual norm Proposition 9.19.)
\begin{solution}

\end{solution}
\end{parts}

\question (O 9.11) 
\begin{parts} 
\part Suppose $\E[X] = 0$. Show that $X$ is $(q, q,0)$-hypercontractive for all $q \geq 1$. 
(Hint: Use monotonicity of norms to reduce to the case $q = 1$.)
\begin{solution}

\end{solution}

\part Show further that $X$ is $(q, q,\rho)$-hypercontractive for all $0 \leq \rho < 1$.
(Hint: Write $(a+\rho X) = (1-\rho) a + \rho(a+X)$ and employ the triangle inequality for $\| \cdot \|_q$.)
\begin{solution}

\end{solution}
\end{parts}

\question (O 9.17) Deduce the $p \leq  2 \leq  q$ cases of the Hypercontractivity Theorem from the $(2, q)$- and $(p,2)$Hypercontractivity Theorems. 
(Hint: Use the semigroup property of $T_{\rho}$, Exercise 2.32.)
\begin{solution}

\end{solution}

\end{questions}
\end{document}