%
% 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{enumerate}
\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 2020}
\bigskip
{\Large Homework 7}
\smallskip
Due: 2:00AM, Saturday, November 7, 2020.
\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] Your term paper topic and partner (if applicable) are due on Gradescope at the same time this homework assignment is. Instructions for the term paper are here: \url{https://cs-people.bu.edu/mbun/courses/535_F20/handouts/term_paper.pdf} and a list of suggested topics is here: \url{https://piazza.com/class/keda2wyieyz10e?cid=277}.
\end{problem}
\medskip
\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$.
\begin{enumerate}[(a)]
\item Show that for every input length $n$, there exists a function $f: \zo^n \to \zo$ that is computed by a circuit of size at most $20n^k$, but not computed by any circuit of size at most $n^k$. Hint: Use the nonuniform hierarchy theorem (Theorem 6.22 in Arora-Barak). (2 points)
\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 of size at most $20|x|^{k}$ that is not computed by any circuit of size at most $|x|^k$. Show that $L \notin \class{SIZE}(n^k)$. (1 point) \begin{solution} Your solution here. \end{solution} \item Show that the language $L \in \class{\Sigma}_4^p$. Conclude that $\class{\Sigma}_4^p \not\subseteq \class{SIZE}(n^k)$. (6 points) \smallskip Hint: $C$ is the lexicographically first circuit of size at most $20n^k$ that is not computed by any circuit of size at most $n^k$ if: $|C| \le 20n^k$ and for all $C' <_{\text{lex}} C$ where $|C'| \le 20n^k$, there 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. (3 points) \begin{solution} Your solution here. \end{solution} \end{enumerate} \end{problem} \bigskip \begin{problem}[$\ZPP$ vs. $\RP \cap \coRP$] Let $L \in \RP \cap \coRP$ be decided by an $\RP$ algorithm $M_0$ and a $\coRP$ algorithm $M_1$, each running in 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$: \begin{quote} On input $x$: \\ Repeat the following indefinitely: \begin{enumerate} \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} We already showed in class that $\ZPP \subseteq \RP\cap \coRP$, so this completes the proof that $\ZPP = \RP \cap \coRP$. (5 points) \end{problem} \begin{solution} Your solution here. \end{solution} \end{document}