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






