\documentclass{article}
\usepackage{amsmath,amssymb}
\usepackage{ulem}
\let\binom=\undefined
\input{preamble.tex}
\begin{document}
\lecture{17}{April 6, 2005}{Madhu Sudan}{Alexey Spiridonov}
\section{$PSPACE\subseteq IP$}
We will show this inclusion using straight-line programs of polynomials
($SPP$). First, we will show that $SPP\subseteq IP$, and then $PSPACE\subseteq SPP$.
In the previous lecture, we showed that the permanent has an interactive
proof, and so $IP\subseteq PSPACE$. Putting the two together, we
will get $IP=PSPACE$. Before carrying out these proofs, we need to
introduce $SPP$.
\subsection{Straight-line programs of polynomials}
Let's start with a quick refresher of straight-line programs ($SP$).
Suppose we have input bits $x_{1},\dots x_{n}$. Then, a straight-line
program is a computation of the following form:\begin{eqnarray*}
y_{1} & \leftarrow & x_{1}+x_{3}\\
y_{2} & \leftarrow & y_{1}\times x_{2}\\
y_{3} & \leftarrow & y_{1}+y_{2}\\
& \cdots\\
y_{i} & \leftarrow & y_{j}\times y_{k}\text{ with }j,k