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

\begin{questions}
\question (O 7.11)
\begin{parts}
\part Let $\phi$ be a CNF of size $s$ and width $w\geq 3$ over variables $x_1, \ldots, x_n$.
Show that there is an ``equivalent" CNF $\phi'$ of size at most $(w-2)s$ and width $3$ over the variables $x_1, \ldots, x_n$ plus auxiliary variables $\Pi_1, \ldots, \pi_{\ell}$ with $\ell \leq (w-3)s$. 
Here ``equivalent" means that for every $x$ such that $\phi(x) = \mathsf{True}$ there exists $\Pi$ such that $\phi'(x, \Pi) = \mathsf{True}$; and, for every $x$ such that $\phi(x) = \mathsf{False}$ we have $\phi'(x, \Pi) = \mathsf{False}$ for all $\Pi$.

\begin{solution}

  \end{solution}

\part Extend the above so that every clause in $\phi'$ has width exactly $3$ (the size may increase by $O(s)$).
\begin{solution}

  \end{solution}
\end{parts}

\question (O 7.12) Suppose there exists an $r$-query PCPP reduction $\mathcal{R}_1$ with rejection rate $\lambda$.
Show that there exists a $3$-query PCPP reduction $\mathcal{R}_2$ with rejection rate at least $\lambda/(r2^r)$. 
The proof length of $\mathcal{R}_2$ should be at most $r2^r \cdot m$ plus the proof length of $\mathcal{R}_1$ (where $m$ is the description-size of $\mathcal{R}_1$’s output) and the predicates output by the reduction should all be logical ORs applied to exactly three literals.

\begin{solution}

  \end{solution}

\question (O 7.17)  Give a $3$-query, length-$O(n)$ PCPP system (with rejection rate a positive universal constant) for the class $\{w_1, w_2 \in \F_2^n \st  (-1)^{w_1 \cdot w_2} = 1\}$.

\begin{solution}

  \end{solution}


\end{questions}

\section*{Lecture 15}

\begin{questions}
\question (O 7.10)
\begin{parts} 
\part Say that $A$ is an $(\alpha, \beta)$-distinguishing algorithm for Max-CSP($\Psi$) if it outputs `YES' on instances with value at least $\beta$ and outputs `NO' on instances with value strictly less than $\alpha$. 
(On each instance with value in $[\alpha, \beta)$, algorithm A may have either output.) 
Show that if there is an efficient $(\alpha, \beta)$-approximation algorithm for Max-CSP($\Psi$), then there is also an efficient $(\alpha, \beta)$-distinguishing algorithm for Max-CSP($\Psi$).
\begin{solution}

\end{solution}

\part Consider Max-CSP($\Psi$), where $\Psi$ be a class of predicates that is closed under restrictions (to nonconstant functions); e.g., Max-$3$-Sat. 
Show that if there is an efficient $(1,1)$-distinguishing algorithm, then there is also an efficient $(1,1)$-approximation algorithm. 
(Hint: Try out all labels for the first variable and use the distinguisher.)
\begin{solution}

\end{solution}
\end{parts}

\question (O 7.20) A randomized assignment for an instance $\mathcal{P}$ of a CSP over domain ­ is a mapping $F$ that labels each variable in $V$ with a probability distribution over domain elements. 
Given a constraint $(S, \psi)$ with $S = (v_1, \ldots, v_r)$, we write $\psi(F(S)) \in [0, 1]$ for the expected value of $\psi(F(v_1), \ldots, F(v_r))$. 
This is simply the probability that $\psi$ is satisfied when one actually draws from the domain-distributions assigned by$F$. 
Finally, we define the value of $F$ to be $\text{Val}_{\mathcal{P}}(F) = E_{S, \psi}[ \psi(F(S))]$.
\begin{parts} 
\part Suppose that $A$ is a deterministic algorithm that produces a randomized assignment of value $\alpha$ on a given instance $\mathcal{P}$. 
Show a simple modification to $A$ that makes it a randomized algorithm that produces a (normal) assignment whose value is $\alpha$ in expectation. (Thus, in constructing approximation algorithms we may allow ourselves to output randomized assignments.)
\begin{solution}

\end{solution}

\part Let $A$ be the deterministic Max-E$3$-Sat algorithm that on every instance outputs the randomized assignment that assigns the uniform distribution on $\{0,1\}$ to each variable. 
Show that this is a $(\frac{7}{8},\beta)$-approximation algorithm for any $\beta$. 
Show also that the same algorithm is a $(\frac{1}{2},\beta)$-approximation algorithm for Max-$3$-Lin.
\begin{solution}

\end{solution}

\part When the domain $\Omega$ ­ is $\{-1, 1\}$, we may model a randomized assignment as a function $f: V \rightarrow [-1, 1]$; here $f(v) = \mu$ is interpreted as the unique probability distribution on $\{-1, 1\}$ which has mean $\mu$. 
Now given a constraint $(S, \psi)$ with $S = (v_1, \ldots, v_r)$, show that the value of $f$ on this constraint is in fact $\psi(f(v_1), \ldots, f(v_r))$, where we identify $\psi: \{-1, 1\}^r \rightarrow \{0, 1\}$ with its multilinear (Fourier) expansion. 
(Hint: Exercise 1.4.)
\begin{solution}

\end{solution}

\part Let $\Psi$ be a collection of predicates over domain $\{-1, 1\}$. 
Let $\nu = \min_{\psi \in \Psi}\{\widehat{\psi}(\emptyset)\}$. 
Show that outputting the randomized assignment $f = 0$ is an efficient $\nu, beta)$-approximation algorithm for Max-CSP($\Psi$).
\begin{solution}

\end{solution}
\end{parts}

\question (O 7.21) Let $F$ be a randomized assignment of value $\alpha$ for CSP instance $\mathcal{P}$ (as in Exercise 7.20). 
Give an efficient deterministic algorithm that outputs a usual assignment  of value at least $\alpha$. 
(Hint: Try all possible labelings for the first variable and compute the expected value that would be achieved if $F$ were used for the remaining variables. 
Pick the best label for the first variable and repeat.)
\begin{solution}

\end{solution}

\end{questions}
\end{document}