%% HOW TO USE THIS TEMPLATE:
%%
%% Ensure that you replace "YOUR NAME HERE" with your own name, in the
%% \studentname command below. Also ensure that the "answers" option
%% appears within the square brackets of the \documentclass command,
%% otherwise latex will suppress your solutions when compiling.
%%
%% Type your solution to each problem part within
%% the \begin{solution} \end{solution} environment immediately
%% following it. Use any of the macros or notation from the
%% header.tex that you need, or use your own (but try to stay
%% consistent with the notation used in the problem).
%%
%% If you have problems compiling this file, you may lack the
%% header.tex file (available on the course web page), or your system
%% may lack some LaTeX packages. The "exam" package (required) is
%% available at:
%%
%% http://mirror.ctan.org/macros/latex/contrib/exam/exam.cls
%%
%% Other packages can be found at ctan.org, or you may just comment
%% them out (only the exam and ams* packages are absolutely required).
% the "answers" option causes the solutions to be printed
\documentclass[11pt,addpoints]{exam}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
% any of the following packages may be safely omitted if they are not
% available on your system (but they should be)
\usepackage{fullpage}
\usepackage{times}
\usepackage{hyperref}
\usepackage{pdfsync}
\usepackage{microtype}
% required macros -- get latest header.tex file from course web page
\input{header}
% VARIABLES
\newcommand{\hwnum}{5}
\newcommand{\duedate}{April 14} % changing this does not change the
% actual due date :)
\newcommand{\studentname}{YOUR NAME HERE}
% END OF SUPPLIED VARIABLES
\hwheader % execute homework commands
\begin{document}
\pagestyle{head} % put header on every page
\noindent This homework is due by the \textbf{start of class on
\duedate} via the
\href{https://t-square.gatech.edu/portal/site/29001.201102/}{course
page on T-Square}. Start early!
\medskip
\noindent \textbf{Instructions.} Solutions must be typeset in \LaTeX\
(a template for this homework is available on the course web page).
Your work will be graded on \emph{correctness}, \emph{clarity}, and
\emph{conciseness}. You should only submit work that you believe to
be correct; if you cannot solve a problem completely, you will get
significantly more partial credit if you clearly identify the gap(s)
in your solution. It is good practice to start any long solution with
an informal (but accurate) ``proof summary'' that describes the main
idea.
\medskip
\noindent You may collaborate with others on this problem set and
consult external sources. However, you must \textbf{\emph{write your
own solutions}} and \textbf{\emph{list your
collaborators/sources}} for each problem.
% QUESTIONS START HERE. PROVIDE SOLUTIONS WITHIN THE "solution"
% ENVIRONMENTS FOLLOWING EACH QUESTION.
\begin{questions}
\question \emph{(Interactive proofs and zero-knowledge.)}
\begin{parts}
\part[5] \emph{(Soundness error is necessary.)} Suppose that a
language $L$ has an interactive proof system $(P,V)$ with
\emph{perfect} soundness, i.e., $V$ never accepts an $x \not\in L$
(no matter what $P^{*}$ does). Prove that $L$ must be in $\NP$.
That is, prove that there is a \emph{deterministic} algorithm $W$,
running in time polynomial in the length of its first argument
$x$, such that $x \in L$ if and only if there exists some
``witness'' $w \in \bit^{*}$ making $W(x,w)$ accept. (\emph{Hint}:
consider a witness consisting of $V$'s entire view.)
In other words, to prove a language that lies outside $\NP$, we
must live with some chance of accepting a ``false theorem.''
\begin{solution}
\end{solution}
\newcommand{\HCP}{\problem{HCP}}
\part[15] An undirected graph $G$ is said to have a
\emph{Hamiltonian cycle} if it contains a cycle that passes
through every vertex exactly once. (That is, the graph has a
``closed loop.'') The Hamiltonian Cycle Problem $\HCP$ is the
language of all graphs $G$ having a Hamiltonian cycle, and is
known to be $\NP$-complete.
Consider the following sketch of an interactive proof $(P,V)$ for
$\HCP$: on a graph $G=(V,E)$ having a Hamiltonian cycle, the
prover first chooses a random permutation $G'$ of $G$. For each
pair of vertices $(i,j) \in V \times V$, the prover sends a
(perfectly binding, computationally hiding) commitment to the bit
$e'_{i,j}$, which is $1$ if $(i,j)$ is an edge in $G'$, and is $0$
otherwise. The verifier replies with a uniformly random challenge
bit $b \gets \bit$. The prover answers the challenge, and the
verifier checks the answer.
Complete the description of the protocol: describe how $P$ answers
$V$'s challenge in both cases ($b=0$ and $b=1$), and how $V$
checks $P$'s answer. Then prove that the protocol is complete and
has soundness error $1/2$. (Why is this an advantage over the
interactive proof for $3$-colorability that we saw in class?)
Finally, describe a (black-box) simulator and sketch a proof that
the protocol is zero-knowledge.
\begin{solution}
\end{solution}
\end{parts}
\question[10] \emph{(Final project status report.)} Write a short
summary (of at most a couple of paragraphs) of your progress so far
on your final project: what specific topic/problem you are
investigating, your findings so far, any obstacles that you have
encountered or foresee, etc. (The more you have accomplished on
your project, the better your report will be!)
\begin{solution}
\end{solution}
\end{questions}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: