%
% 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 9}
\smallskip
Due: 2:00AM, Saturday, December 5, 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
\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 \notin 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
\newcommand{\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 \ne 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 \ k\text{-colorings}\} \in \IP$.
(6 points)
\begin{solution}
Your solution here.
\end{solution}
\end{enumerate}
\end{document}