%
% 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 7}

\smallskip

Due: 11:59PM, Tuesday, November 6, 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


\begin{problem}[Circuit Lower Bounds for $\class{PH}$]
	In this problem, you will prove that $\class{PH}$ can compute languages with high circuit complexity. Specifically, you will show that for every integer $k \ge 1$, there is a language in $\class{\Sigma}_2^p$ that cannot be computed by circuits of size at most $n^k$. (Curiously, this is a non-constructive proof...we know the language exists, but we don't know what it is. For more context, note that the best circuit size lower bound we have for $\SAT$ is roughly $5n$.)
	\begin{enumerate}[label=(\alph*)]
		
		
		\item Show that for every sufficiently large $n$, there exists a function $f: \zo^n \to \zo$ that is computed by a circuit of size at most $n^{k+1}$, but not computed by any circuit of size at most $n^k$. Hint: Use the nonuniform hierarchy theorem (Theorem 6.22 in Arora-Barak). (1 point)
		
		\begin{solution}
			Your solution here.
		\end{solution}
	
		\item Let $C, C'$ be circuits, both on $n$-bit inputs. Say that $C'$ comes lexicographically before $C$, written $C' <_{\text{lex}} C$, if the string encoding $C'$ precedes the string encoding $C$ in the lexicographic ordering. Define the language $L$ to consist of all strings $x$ such that $C(x) = 1$, where $C$ is the lexicographically first circuit (on $|x|$-bit inputs) of size at most $|x|^{k+1}$ that is not computed by any circuit of size at most $|x|^k$.
		
		By construction, we have that $L \notin \class{SIZE}(n^k)$. Show that the language $L \in \class{\Sigma}_4^p$, and thereby conclude that $\class{\Sigma}_4^p \not\subseteq \class{SIZE}(n^k)$.  (6 points)
		
		\begin{solution}
			Your solution here.
		\end{solution}
		
		Hint: $C$ is the lexicographically first circuit of size at most $n^{k+1}$ that is not computed by any circuit of size at most $n^k$ if: $|C| \le n^{k+1}$ and \emph{for all} $C' <_{\text{lex}} C$ where $|C'| \le n^{k+1}$, there \emph{exists} a smaller circuit $C''$ of size $\le n^k$ such that $C'' \equiv C'$.
		
		\begin{solution}
			Your solution here.
		\end{solution}
	
		\item Combine part (c) with the Karp-Lipton Theorem ($\NP \subseteq \Ppoly \implies \class{PH} = \class{\Sigma}_2^p$) to show that $\class{\Sigma}_2^p \not\subseteq \class{SIZE}(n^k)$. (3 points)
		
		\begin{solution}
			Your solution here.
		\end{solution}
	
		\item Does part (d) imply $\class{\Sigma}_2^p \not\subseteq \Ppoly$?  Explain your answer. (2 points)
	
		\begin{solution}
		Your solution here.
		\end{solution}
	\end{enumerate}
\end{problem}


\bigskip


\begin{problem}[Characterizing $\ZPP$] Recall that we defined the class $\ZPP$ to consist of languages that are decidable by probabilistic TMs in expected polynomial time. In this problem, you will explore two different alternative characterizations of this class.
	
	\begin{enumerate}[label=(\alph*)]
	\item First, let us complete the proof we started in class (Thursday, 11/2) that $\ZPP = \RP \cap \coRP$. We already showed in class that $\ZPP \subseteq \RP \cap \coRP$. For the opposite containment, let $L \in \RP \cap \coRP$ be decided by an $\RP$ algorithm $M_0$ and a $\coRP$ algorithm $M_1$, each running in (worst-case) time $p(n)$ for some polynomial $p$. Show that the following is a zero-error randomized algorithm deciding $L$ in expected polynomial time, and thus $\RP\cap \coRP\subseteq \ZPP$. (4 points)
	\begin{quote}
		On input $x$: \\
		Repeat the following indefinitely:
		\begin{enumerate}[label=\arabic*.]
			\item Run $M_0$ on input $x$. If it accepts, accept; else, continue.
			\item Run $M_1$ on input $x$. If it rejects, reject; else, continue.
		\end{enumerate}
	\end{quote}

	
	\begin{solution}
		Your solution here.
	\end{solution}


	\item An \emph{abstaining} probabilistic TM is like a normal probabilistic TM for a decision problem, except that it may output any of the answers $0, 1$, or $?$ (standing for ``I abstain from answering''). Show that a language $L \in \ZPP$ if and only if there exists a abstaining probabilistic TM $M$ running in \emph{worst-case} polynomial time such that
	\begin{itemize}
		\item If $x \in L$, then on input $x$, the TM $M$ always outputs either $1$ or $?$,
		\item If $x \notin L$, then on input $x$, the TM $M$ always outputs either $0$ or $?$, and
		\item For every input $x$, we have $\Pr[M(x) =\ ?] \le 1/3$.
	\end{itemize}
	That is, when $M$ produces an answer of 0 or 1, it is always correct, and on every input it abstains from answering with probability at most $1/3$. (4 points)
	
	\begin{solution}
		Your solution here.
	\end{solution}

	\end{enumerate}
\end{problem}



\end{document}






