\documentclass{article}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{8.5in}
\newcommand{\header}[5]{
\renewcommand{\thepage}{\arabic{page}}
\noindent
\begin{center}
\framebox{
\vbox{
\hbox to 5.78in {\bf {#1} \hfill {#2}}
\vspace{2mm}
\hbox to 5.78in { {\Large \hfill Lecture {#3}\hfill} }
\vspace{2mm}
\hbox to 5.78in { {\it Instructor: {#4} \hfill Scribe: {#5}} }
}
}
\end{center}
\vspace*{3mm}
}
\newcommand{\ip}{\hbox{\bf IP}}
\newcommand{\mip}{\hbox{\bf MIP}}
\newcommand{\oip}{\hbox{\bf OIP}}
\newcommand{\pspace}{\hbox{\bf PSPACE}}
\newcommand{\nexp}{\hbox{\bf NEXP}}
\newcommand{\corp}{\hbox{\bf co-RP}}
\newcommand{\np}{\hbox{\bf NP}}
\newcommand{\pcp}{\hbox{\bf PCP}}
\newcommand{\Z}{\hbox{\bf Z}}
\newcommand{\poly}{\hbox{poly}}
\begin{document}
\header{6.841/18.405J: Advanced Complexity}{Wednesday, April 2, 2003}
{Lecture 14}{Madhu Sudan}{Dion Harmon}
In this lecture we cover
\begin{itemize}
\item $\ip = \pspace$
\begin{itemize}
\item Interactive proof for straightline programs.
\item Straightline program for $\pspace$.
\end{itemize}
\item Other definitions of proofs (and nice applications).
\begin{itemize}
\item Multi-prover interactive proofs ($\mip$) and $\mip=\nexp$.
\item Oracle Interactive Proofs.
\item Probabilistically Checkable Proofs (PCP's).
\end{itemize}
\end{itemize}
\section{$\ip = \pspace$}
We have left to show that $\pspace\subseteq \ip$. We do this by using
straightline programs of polynomials. We first show there is an
interactive proof to evaluate any straightline program of a certain
type and then show that any $L\in\pspace$ has a nice straightline
program of the same type.
\subsection{Straightline Programs of Polynomials}
A straightline program of polynomials is characterized by four
parameters: $n$, $L$, $w$, and $d$.
\begin{description}
\advance\leftskip by 0.5in
\item[$n$] The number of variables.
\item[$L$] The number of polynomials (minus 1).
\item[$w$] The width of the program.
\item[$d$] The degree of the program.
\end{description}
The program consists of polynomials $P_0,\ldots,P_L$ each of degree at
most $d$ in at most $n$ variables. Polynomial $P_i$ is easy to evaluate in
polynomial time with at most $w$ calls to $P_{i-1}$. We will deal with $w=2$
today. We are interested in verifying claims of the form $P_L(z)=a$.
\subsection{Lines in $\Z_p^n$}
Algebraically a line in $\Z_p^n$ is a set
\begin{equation}
\label{eqn:line-zp}
\ell_{xy} = \left\{\left.\ell_{xy}(t)\right|t\in\Z_p\right\}
=
\left\{\left.\left[
\begin{array}{c}
(1-t)x_1+y_1\\
(1-t)x_2+y_2\\
\vdots\\
(1-t)x_n+y_n\\
\end{array}\right]\right|t\in\Z_p\right\}
\end{equation}
where $x$ and $y$ are elements of $\Z_p^n$. The definition of a
function $p$ from $\Z_p^n$ to $\Z_p^n$ restricted to a line is now
straightforward:
$$
\begin{array}{rcl}
p&:&\Z_p^n\mapsto\Z_p\\
p|_\ell&:&\Z_p\mapsto\Z_p \quad\hbox{such that}\quad
p|_\ell(t) = p(\ell(t)).\\
\end{array}
$$
where $\ell(t)$ is defined as in equation~(\ref{eqn:line-zp}). Note
that if a function $P$ has degree $d$ in $\Z_p^n$ then the restriction
of $P$ to a line $\ell$ has the same degree (in $x$, $y$, and $t$
variables).
\subsection{Interactive Proof for some width 2 straightline programs.}
\label{sec:w2-straight}
We consider straightline programs of the form
$$
P_i(x) = P_{i-1}(f_i(x))\ \ \sigma_i \ \ P_{i-1}(g_i(x))
$$
where $\sigma_i\in\{+,\cdot\}$ and $f_i$ and $g_i$ are polytime
computable.
We want to see if $P_L(z_L)=a_L$. For the first step we do the following:
\begin{description}
\item[Round 1:]Both $V$ and $P$ compute $x_L=f_L(z_L)$ and
$y_L=g_L(z_L)$.
\item[Round 2:] $P$ sends $V$ a polynomial $h_L(t)$ which is supposed
to be $P_{L-1}(\ell_{x_L,y_L}(t))$.
\item[Round 3:] $V$ checks to make sure that $a_L=h_L(0)\ \sigma_L\
h_L(1)$. If not, $V$ rejects. Otherwise $V$ picks $t_L$ randomly
in $\Z_p$. Let $z_{L-1}=\ell_{x_L,y_L}(t_L)$ and
$a_{L-1}=h_L(t_L)$.
\end{description}
$P$ and $V$ verify recursively that $P_{L-1}(z_{L-1})=a_{L-1}$. We end
at the question, ``Does $P_0(z_0)=a_0$?'' and the verifier can compute
this in poly time.
This is sound and complete:
\begin{description}
\item[Completeness] The prover is honest and computes $h_i=P_i|\ell_i$
at each step and the verifier will not reject: we accept with
probability 1.
\item[Soundness] If $P_i(z_i)\ne a_i$ and the verifier does not reject
during step $L-i+1$ then with probability $1-d/p$
$P_{i-1}(z_{i-1})\ne a_{i-1}$ and the inequality is preserved. The
inequality is preserved with probability $(1-d/p)^L\ge 1-dL/p$
through all steps. The verifier checks for itself if
$P_0(z_0)=a_0$. If $P_L(z_L)\ne a_L$ it will discover $P_0(z_0)\ne
a_0$ with probability $\ge 1-dL/p$. Picking $p$ larger than $2dL$
gives us the necessary bound.
\end{description}
\section{Straightline polynomials produce all of $\pspace$}
\subsection{Description of polynomials used}
We use only the types of polynomials described at the beginning of
section~\ref{sec:w2-straight}. Our polynomials are $P_i(x,y)$ and
$Q_{i,j}(x,y,z_1,\ldots,z_j)$, where $x$ and $y$ are length $n$
vectors in $\Z_p^n$ and $z_i\in\Z_p$. If the input vectors $x$ and
$y$ are length $n$ bit vectors (0's and 1's) then we interpret them as
configurations of some $\pspace$ machine $M$. The vectors $x$ and $y$
have no special meaning if they are not bit vectors. For state
vectors $x$ and $y$ let
$$
P_i(x,y)=\left\{
\begin{array}{rl}
1&\ \hbox{if $M$ goes from $x$ to $y$ in exactly $2^i$ steps}\\
0&\ \hbox{otherwise}\\
\end{array}\right.
$$
To get $P_{i}$ from $P_{i-1}$, consider some state $z$ that is halfway
between $x$ and $y$ in the execution of $M$. We have
$P_{i-1}(x,z)=P_{i-1}(z,y)=1$. Execution of $M$ is deterministic so
there is only one such $z$ (in $\{0,1\}^n$). Thus
$$
P_{i}(x,y)=\sum_{\hbox to 0pt{\hss$\scriptstyle z\in\{0,1\}^n$\hss}}
P_{i-1}(x,z)\cdot P_{i-1}(z,y).
$$
It takes exponential time to sum over all such $z$ so we use the
$Q_{i,j}$ polynomials to evaluate the sum efficiently:
$$
\begin{array}{rcl}
Q_{i,n}(x,y,\underbrace{z_1,\ldots,z_n}_{z\in\Z_p^n})&=&
P_{i-1}(x,z)\cdot P_{i-1}(z,y)\\
Q_{i,j}(x,y,z_{1},\ldots,z_j)&=&Q_{i,j+1}(x,y,z_1,\ldots,z_j,0) +
Q_{i,j+1}(x,y,z_1,\ldots,z_j,1)\\
\end{array}
$$
Thus
$$
Q_{i,0}=\sum_{z\in\{0,1\}^n}P_{i-1}(x,z)\cdot P_{i-1}(z,y)=P_{i}(x,y).
$$
Our polynomials (in order) for the straightline program are
$$
P_{0}, Q_{1,n}, \ldots, Q_{1,0}, P_{1}, Q_{2,n},\ldots,Q_{2,0},P_{2},
\ldots,P_{L}.
$$
Our program has width $2$ and length $n^2$. The degree of this
straightline program is discussed below.
\subsection{Degree of $P_0$}
We can give $P_0$ explicitly in terms of single step of the machine:
$$
P_0(x,y) =
\prod_{j=1}^{n}\left(
\vcenter{\vskip0.2cm\hbox{\hskip0.04cm\setlength{\unitlength}{0.7cm}
\begin{picture}(3,2)
\put(0,2){\line(1,0){3}}
\put(0,1){\line(1,0){1}}
\put(2,1){\line(1,0){1}}
\put(1,0){\line(1,0){1}}
\put(0,1){\line(0,1){1}}
\put(3,1){\line(0,1){1}}
\put(1,0){\line(0,1){1}}
\put(2,0){\line(0,1){1}}
\put(0,1){\makebox(1,1){\hfil$x_{i-1}$}}
\put(1,1){\makebox(1,1){$x_{i}$}}
\put(2,1){\makebox(1,1){$x_{i+1}$\hfil}}
\put(1,0){\makebox(1,1){$y_i$}}
\end{picture}\hskip0.1cm}\vskip0.1cm}
\right)
$$
where $n$ is the total amount of space used in the computation. The
polynomial represented by
$$
\vcenter{\vskip0.2cm\hbox{\hskip0.04cm\setlength{\unitlength}{0.7cm}
\begin{picture}(3,2)
\put(0,2){\line(1,0){3}}
\put(0,1){\line(1,0){1}}
\put(2,1){\line(1,0){1}}
\put(1,0){\line(1,0){1}}
\put(0,1){\line(0,1){1}}
\put(3,1){\line(0,1){1}}
\put(1,0){\line(0,1){1}}
\put(2,0){\line(0,1){1}}
\put(0,1){\makebox(1,1){\hfil$x_{i-1}$}}
\put(1,1){\makebox(1,1){$x_{i}$}}
\put(2,1){\makebox(1,1){$x_{i+1}$\hfil}}
\put(1,0){\makebox(1,1){$y_i$}}
\end{picture}\hskip0.1cm}\vskip0.1cm}
$$ is one if $y_i$ is the appropriate bit given the $x$ bits and $0$
otherwise. It is of some constant degree at most $D$ in $x_i$'s and
$y_i$'s. The degree of $P_0(x,y)$ in any one $x$ variable is at most
$3D$ and $D$ in any $y$ variable. Thus $P_0(x,y)$ is of degree at most $3nD$
which is polynomial in the input size.
\subsection{Degree of other polynomials}
Assume $P_{i-1}$ is of degree at most $d$ in any one variable (the
total degree may be $nd$). The expression for $Q_{i,n}$ indicates it
can be degree at most $d$ in any $x$ or $y$ variables and $2d$ in any
$z$. The sums to get $Q_{i,j}$'s for $j