\documentclass[12pt]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%TCIDATA{TCIstyle=misc/misc.lat,scratch,scratch}
%TCIDATA{Created=Wed Mar 11 14:55:15 1998}
%TCIDATA{LastRevised=Wed Apr 15 22:16:02 1998}
%TCIDATA{Language=American English}
\input{preamble}
\input{tcilatex}
\begin{document}
\lecture{17}{April 14, 1998}{Daniel A. Spielman}{Anna Charny}
Today we will begin a completely new topic. We shall study Interactive
Proofs.
The notion of interactive proofs was designed to capture
those languages in which one can be convinced of membership.
This conviction may be obtained through communication rather
than the mere presentation of a proof.
\section{Publishable Proofs}
The first topic we will study is \emph{Publishable Proofs}, introduced by
Babai. The idea is to reduce the problem to some probabilistic statement
that can be (probabilistically)\ verified. We have actually seen publishable
proofs in the last homework. Indeed, $\sum \cdot BP\cdot P$ is really what a
publishable proof is. That is, $L$ has publishable proofs (i.e. $L\in \sum
\cdot BP\cdot P)$ iff there exists a polynomial time Turing Machine $V$
(which we shall call a \emph{verifier}) such that
$w\in L\Longrightarrow \exists x$ s.t. for at least $2/3$ of all choices of $%
y$ $V(w,x,y)$ accepts
$w\notin L\Longrightarrow \forall x$ for at most $1/3$ of all choices of $y$
$V(w,x,y)$ accepts,
where $|x|$ and $|y|$ are polynomial in $|w|.$
\section{Interactive Proofs}
Publishable proofs is just one approach to the problem. \emph{Interactive
Proofs} is another.
The idea of Interactive Proofs can be described as follows. Suppose you have
a conversation between two parties. One party is an ''all-powerful'' \emph{%
Prover}, which we denote by $P$. The Prover is a ''really smart being'',
which can be described by an arbitrary function. The second party to the
conversation is \emph{Verifier, }which we denote by $V.$ The Verifier is a
polynomial time Turing Machine, which has access to randomness in the sense
that it can toss random coins and ask different questions depending on the
outcome. The coins are kept \emph{private} to the Verifier. The conversation
is a sequence of ''questions'' and ''answers'' between $V$ and $P$ in which
the Prover is trying to convince the Verifier of some statement by answering
the Verifier's questions.
It is essential that $V$ has access to randomness because otherwise we will
never escape $NP$. In the absence of randomness available to $V$, $P$ can
predict exactly what $V$ will ask and precompute the whole sequence of
questions and answers, so in fact $V$ would not be needed. If $V$ can toss
coins, however, $P$\ cannot predict what the question is going to be.
One example of what Interactive Proofs are is graph \emph{non-isomorphism}.
Recall that two graphs $G$, $H$ are called \emph{isomorphic} if there exists
a permutation $\pi $ of vertices of graph $G$ satisfying $\pi (G)=H.$
We define $NONISO$\ as a language of all pairs of graphs $(G,H)$ such that $%
G $\ and $H$ are \textbf{not} isomorphic. How do we constuct an interactive
proof for $NONISO$? In general, how do we construct interactive proofs?
A simple example of an interactive proof is a protocol for convincing a
colorblind friend that colors exist. The protocol is as follows. You get two
balls of different color (say red and blue) which are otherwise identical.
You give the balls to your colorblind friend and tell him that he has a red
ball in his right hand and a blue ball in his left hand. The friend then
hides the balls behind his back and randomly shuffles them, so that he knows
which ball is in which hand but you don't. He then shows
them to you and you correctly identify the balls.
We now give an interactive proof for $NONISO.$ We specify the protocol by
which $P$ will convince $V$ that two graphs $G$ and $H$ are non-isomorphic.
We assume that $G$ and $H$ have the same number of vertices, since
otherwise the graphs are obviously non-isomorphic. Let $n$ denote the number
of vertices of either graph.
Actions for $V$:
\begin{enumerate}
\item Flip a random bit $b\in \{0,1\}$; $b$ is a ''fair'' coin with
probability $1/2$ of either outcome.
\item Choose a permutation $\pi $ of $\{1,2,...n\}.$ If
$b=0$ show the Prover $\pi
(G).$ Otherwise show $\pi (H)$
\end{enumerate}
In response the Prover says which graph is being shown to it.
This can be repeated as many times as needed to boost confidence. As long as
the prover guesses correctly, the verifier should become
confident that graphs are non-isomorphic.
\textbf{Proof of Correctness}.
We use notation $(V,P)$\ to denote the outcome of the protoocol.
If $G$ is not isomorphic to $H$ then there exists a prover $P$ s.t. $Pr[(V,P)
$ accept$]=1$
If $G$ is isomorphic to $H$, then for any P,
on $k$ runs of the protocol $Pr[(V,P)$
accept$] \leq \frac 1{2^k}.$ The latter is because $P$\ cannot distinguish
between two isomorphic graphs.
In general, the key elements of an Interactive Proof are
\begin{enumerate}
\item players $V$ and $P$ take turns
\item after a certain number of turns they stop and $V$ decides whether to
accept or reject.
\end{enumerate}
We can treat $V$ as a function $V(w,r,C)\rightarrow \{S,accept,reject\},$
where $w$ is an input string, $r$ is a random string and $C$ and $S$ are
strings denoting respectively the conversation so far and $V$'s response.
More specifically, the output of this function is defined as follows:
if $C=\varepsilon $ output $S=V_1$
if $C=V_1,P_1,...V_i,P_i$ and $i