[SOLVED] CS algorithm %

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

definclsolns{0}
documentclass[12pt]{article}

usepackage{fullpage}
usepackage{graphicx}
usepackage{enumerate}
usepackage{comment}
usepackage{amsmath,amssymb,amsthm}
usepackage{hyperref}

input{macros}

theoremstyle{definition}

ifnuminclsolns=1
ewenvironment{solution}{paragraph{Solution.}}{}
else
ewenvironment{solution}{}{}
excludecomment{solution}
fi

makeatletter
defcollaborators#1{gdef@collaborators{#1}}
def@collaborators{@latex@warning@no@line{No
oexpandcollaborators 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}

ifnuminclsolns=1
makeatletter
oindent 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
otin 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
otsubseteq class{SIZE}(n^k)$. (6 points)smallskipHint: $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
otsubseteq class{SIZE}(n^k)$. (3 points)begin{solution}Your solution here.end{solution}item Does part (d) imply $class{Sigma}_2^p
otsubseteq Ppoly$?Explain your answer. (3 points)begin{solution}Your solution here.end{solution}end{enumerate}end{problem}bigskipbegin{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 $RPcap coRPsubseteq 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 RPcap coRP$, so this completes the proof that $ZPP = RP cap coRP$.(5 points)end{problem}begin{solution}Your solution here.end{solution}end{document}