[SOLVED] CS %

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

smallskip

Due: 2:00AM, Saturday, December 5, 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

begin{problem}[Perfect Interactive Proofs] For parameters $c, s ge 0$, define the class $MA_{c, s}$ to consist of Merlin-Arthur interactive proofs with completeness probability $c$ and soundness probability $s$. That is, a language $L in MA_{c, s}$ if there exists a probabilistic poly-time verifier $V$ and a polynomial $m(n)$ such that
begin{align*}
x in L &implies exists u in zo^{m(n)} Pr[V(x, u) = 1] ge c \
x
otin L &implies forall u in zo^{m(n)} Pr[V(x, u) = 1] le s.
end{align*}
Recall that in class we defined $class{MA} = class{MA}_{2/3, 1/3}$.
begin{enumerate}[(a)]

item Prove that $MA_{1, 1/3} = MA$. That is, we may assume Merlin-Arthur proofs have perfect completeness probability. Hint: Modify the proof of the Sipser-G'{a}cs Theorem (Theorem 7.15). (6 points)

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

item Prove that $MA_{2/3, 0} = NP$. That is, Merlin-Arthur proofs with perfect soundness are no more powerful than deterministic proofs. (4 points)
begin{solution}
Your solution here.
end{solution}

item *Bonus* Prove the same relationships for general interactive proofs. That is, show that $IP_{1, 1/3} = IP$ and $IP_{2/3, 0} = NP$.
begin{solution}
Your solution here.
end{solution}
end{enumerate}
end{problem}

bigskip

ewcommand{perm}{operatorname{perm}}
begin{problem}[Counting $k$-Colorings]
Let $G = ([n], E)$ be a graph on $n$ vertices. A $k$-coloring of $G$ is a vector of colors $(c_1, dots, c_n) in [k]^n$ such that for every edge $(i, j) in E$, we have $c_i
e c_j$.
end{problem}

begin{enumerate}[(a)]

item Show that there is a rational polynomial $p$ of degree $poly(k, n)$ such that the number of $k$-colorings of a graph $G$ is given by
[sum_{c_1 = 1}^k sum_{c_2 = 1}^k ldots sum_{c_n = 1}^k p(c_1, dots, c_n).]
Hint: url{https://en.wikipedia.org/wiki/Lagrange_polynomial}. (4 points)

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

item Modify the sumcheck protocol to show that for every constant $k$, the language $mathprob{#kCOL_D} = {langle G, t rangle mid G text{ has exactly } t ktext{-colorings}} in IP$.
(6 points)

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

end{document}