%
% To use this as a template for turning in your solutions, change the flag
% \inclsolns from 0 to 1. Make sure you include macros.tex in the directory
% containing this file. Edit the "author" and "collaborators" fields as
% appropriate. Write your solutions where indicated.
%

\def\inclsolns{0}
\documentclass[12pt]{article}

\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{enumitem}
\usepackage{comment}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{hyperref}

\input{macros}

\theoremstyle{definition}

\ifnum\inclsolns=1
\newenvironment{solution}{\paragraph{Solution.}}{}
\else
\newenvironment{solution}{}{}
\excludecomment{solution}
\fi


\makeatletter
\def\collaborators#1{\gdef\@collaborators{#1}}
\def\@collaborators{\@latex@warning@no@line{No \noexpand\collaborators given}}
\makeatother

\author{Ada Lovelace}
\collaborators{Charlie Babbage, Mike Faraday}

\begin{document}


\begin{center}
{\Large CS 535: Complexity Theory, Fall 2023}

\bigskip

{\Large Homework 8}

\smallskip

Due: 11:59PM, Tuesday, November 15, 2023.

\end{center}

\ifnum\inclsolns=1
	\makeatletter
	\noindent Name: \@author \\
	Collaborators: \@collaborators
	\makeatother
\else
\fi

\paragraph{Reminder.}
Homework must be typeset with \LaTeX\ preferred. Make sure you understand the course collaboration and honesty policy before beginning this assignment. Collaboration is permitted, but you must write the solutions {\em by
	yourself without assistance}. You must also identify your
collaborators. Assignments missing a collaboration statement will not be accepted. Getting solutions from outside sources such as the
Web or students not enrolled in the class is strictly forbidden.

\bigskip

\setcounter{problem}{-1}
\begin{problem}[Term Paper]
	Reminder that a draft of your term paper is due on Tuesday, Nov. 21. Of course it's ``just'' a draft, but the more fleshed out it is, the more useful feedback we (and your classmates) will be able to give you.
\end{problem}

\begin{problem}[Consequences of Valiant-Vazirani]
	Recall the Valiant-Vazirani Theorem, which says that there is a probabilistic polynomial-time algorithm $A$ that takes as input an $n$-variable Boolean formula $\phi$ and outputs another $n$-variable formula such that
	\begin{align*}
		\varphi \in \SAT &\implies \Pr[A(\varphi) \in \mathprob{USAT}_Y] \ge \frac{1}{8n} \\
		\varphi \notin \SAT &\implies \Pr[A(\varphi) \in \mathprob{USAT}_N] = 1.
	\end{align*}
	\begin{enumerate}[label=(\alph*)]
		\item Adapt Definition 7 ($\class{PromiseBPP}$)  from Lecture Notes 17 to the class $\RP$ to define an analogous class $\class{PromiseRP}$. (1 point)
		\begin{solution}
			Your solution here.
		\end{solution}
		\item Use the VV Theorem to show that $\NP = \RP$ if and only if $\mathprob{USAT} \in \class{PromiseRP}$. (3 points)
		\begin{solution}
			Your solution here.
		\end{solution}
	
		\item (*Individual Review: No collaboration allowed for this part only*) A \emph{non-adaptive} oracle Turing machine $M^{\mathcal{O}}$ may  write a sequence of strings $q_1, \dots, q_k$ to its oracle tape and \underline{in at most one point in its computation} obtain the sequence of answers $\mathcal{O}(q_1), \dots, \mathcal{O}(q_k)$ (where $\mathcal{O}(q_i)$ stands for the answer to the question ``Is $q_i \in \mathcal{O}$?''). That is, all the queries to the oracle have to be issued in a single batch, so the selection of a query cannot depend on the answers to previous queries.
		
		Describe a deterministic poly-time non-adaptive oracle TM $M^{\mathprob{SAT}}$ that, given a Boolean formula $\varphi \in \mathprob{USAT}_Y$, outputs a satisfying assignment to $\varphi$ after making $O(n)$ queries to its $\SAT$ oracle. (2 points)

		(No need to explain correctness or runtime for this problem, as long as they're reasonably clear from the description of your algorithm.)
		\begin{solution}
			Your solution here.
		\end{solution}
	
		\item Use part (c) and the VV Theorem to describe a \emph{randomized} poly-time non-adaptive oracle TM $R^{\SAT}$ that, given a Boolean formula $\varphi \in \SAT$, outputs a satisfying assignment to $\varphi$ with probability at least $\Omega(1/n)$ after making $O(n)$ queries. (2 points)
		
		(No need to explain correctness or runtime for this problem, as long as they're reasonably clear from the description of your algorithm.)
	
		\begin{solution}
		Your solution here.
		\end{solution}
	\end{enumerate}
\end{problem}


\bigskip


\begin{problem}[Approximate Counting with an $\NP$ Oracle] As we'll see on Thursday, an important technical tool in the proof of the VV Theorem is \emph{pairwise independent hash functions}. In the following problem, you may assume that for every $k \le n$, there is a family of functions $\mathcal{H}_{n, k}$ such that for every pair of inputs $x, x' \in \zo^n$ and every pair of possible outputs $y, y' \in \zo^k$, we have
	\[\Pr_{h \gets \mathcal{H}_{n, k}} [ h(x) = y \land h(x') = y'] = \Pr_{h \gets \mathcal{H}_{n, k}} [ h(x) = y ] \cdot \Pr_{h \gets \mathcal{H}_{n, k}}[h(x') = y'] = 2^{-k} \cdot 2^{-k} = 2^{-2k}.\]
Moreover, each function $h$ can be described by a $\poly(n)$-size circuit (and hence, be evaluated efficiently), and can be sampled from $\mathcal{H}_{n, k}$ in $\poly(n)$ time.
	
	\begin{enumerate}[label=(\alph*)]
	\item Show that for every subset $S \subseteq \zo^n$, and every parameter $t > 0$, we have
	\[\Pr_{h \gets \mathcal{H}_{n, k}} \left[\left||\{x \in S \mid h(x) = 0^k\}| - 2^{-k} \cdot |S| \right| \ge t\right] \le \frac{1}{t^2} \cdot 2^{-k} \cdot |S|.\]
	
	 Hint: The expression $|\{x \in S \mid h(x) = 0^k\}|$ counts the number of elements in $S$ that hash to the all-$0$ string. The all-$0$ string is one out of $2^k$ possible hash images, so the expression $2^{-k} \cdot |S|$ is the expected value of this quantity. So this statement just says that the number of elements that hash to 0 concentrates around its expectation. Use Chebyshev's inequality to control this. Another helpful fact here is that that if $X_1, \dots, X_m$ are pairwise independent random variables, i.e., $\Pr[X_i = a \land X_j = b] = \Pr[X_i = a] \cdot \Pr[X_j = b]$ for all $i, j, a, b$, then $\Var[\sum_{i = 1}^m X_i] = \sum_{i=1}^m \Var[X_i]$. 	(6 points)
	
	\begin{solution}
		Your solution here.
	\end{solution}


	\item For a Boolean circuit $C : \zo^n \to \zo$, define $F(C) = |\{x \in \zo^n \mid C(x) = 1\}|$ to count the number of inputs that cause $C$ to evaluate to $1$. Use part (a) to show that the following problem $\mathprob{ApxC}$ (short for approximate counting) is in $\class{PromiseBPP}^{\NP}$:
	\begin{align*}
		\mathprob{ApxC}_Y &= \{\langle C, k \rangle \mid F(C) \ge 8 \cdot 2^{k}\} \\
		\mathprob{ApxC}_N &= \left\{\langle C, k \rangle \mid F(C) \le \frac{1}{8} \cdot 2^{k}\right\}.
	\end{align*}

	Hint: Use the fact that the satisfiability problem for Boolean circuits is in $\NP$.	(6 points)
	
	\begin{solution}
		Your solution here.
	\end{solution}
	
	\item (Bonus Problem)
	Use part (b) to show that there exists a constant $\alpha > 0$ and a poly-time randomized $\NP$-oracle algorithm that, given as input a Boolean circuit $C$, estimates $F(C)$ to within a multiplicative factor of $\alpha$ with probability at least $3/4$. That is,
	\[\Pr\left[\frac{1}{\alpha} \cdot F(C) \le M^A(C) \le \alpha \cdot F(C)\right] \ge \frac{3}{4}.\]
	
	\begin{solution}
		Your solution here.
	\end{solution}


	\item (Bonus Problem)
	Show that there is a poly-time randomized $\NP$-oracle algorithm that, given as input a Boolean circuit $C$, outputs $\bot$ with probability at most $1/2$ and, conditioned on not outputting $\bot$, outputs a uniformly random $x$ for which $C(x) = 1$.
	
	\begin{solution}
		Your solution here.
	\end{solution}

	\end{enumerate}
\end{problem}



\end{document}






