\documentclass{article}
\usepackage{amsmath,amsthm}
\usepackage{graphicx}
\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{\PsP}{\text{P}^{\text{\#P}}}

\newtheorem*{todatheorem}{Toda's Theorem}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{lpart}{Part}[lemma]

\begin{document}

\header{6.841/18.405J Advanced Complexity Theory}{March 17, 2003}
{11: Toda's Theorem Continued}
{Prof. Madhu Sudan}{Ed Solovey}

{\bf Last Time}

\begin{itemize}

\item Defined \#P

\item Discussed Operators on Complexity Classes

\item Began Toda's Theorem

\end{itemize}

{\bf Today}

\begin{enumerate}

\item Toda's Theorem (continued)

\item Introduce Interactive Proofs

\end{enumerate}


\section{Toda's Theorem}

{\bf Toda's Theorem.}  $\text{PH}\subseteq\PsP$

We will prove Toda's theorem in two parts:

\begin{itemize}

\item {\bf Part I}  $\text{PH}\subseteq\text{BP}\cdot\oplus\cdot\text{P}$

\item {\bf Part II}  $\text{BP}\cdot\oplus\cdot\text{P}\subseteq\PsP$

\end{itemize}

 We will eventually see that we only need to make one call to the \#P oracle. 

\subsection{Part I - $\text{PH}\subseteq\text{BP}\cdot\oplus\cdot\text{P}$}

We will prove this in several steps.  

\begin{align*}
\exists\cdot\text{BP}\cdot\oplus\cdot\text{P} & \subseteq\text{BP}\cdot\oplus\cdot\text{BP}\cdot\oplus\cdot\text{P} && \text{[Step 1]}\\
& \subseteq\text{BP}\cdot\text{BP}\cdot\oplus\cdot\oplus\cdot\text{P} && \text{[Step 2]}\\
& \subseteq\text{BP}\cdot\text{BP}\cdot\oplus\cdot\text{P} && \text{[Step 3]}\\
& \subseteq\text{BP}\cdot\oplus\cdot\text{P} && \text{[Step 4]}
\end{align*}

Since $\exists\cdot\mathcal{C} = \neg\cdot\forall\cdot\mathcal{C}$, we can see that any level of the hierarchy can be expressed as

$\text{BP}\cdot\oplus\cdot\text{BP}\cdot\oplus\cdot\text{BP}\cdot\oplus\cdot\text{BP}\cdot\oplus\dots\cdot\text{P}$, and by the steps above this can be expressed as,

$\text{BP}\cdot\oplus\cdot\text{P}$.  Implying that $\text{PH}\subseteq\text{BP}\cdot\oplus\cdot\text{P}$.  Note that it is a necessary and satisfied condition that the class P is closed under all of the above operators.  

\paragraph{}In the steps below we will think of operations on complexity classes as circuits, with each operator corresponding to gates of a particular type.  Although the gates may have exponential fan-in, the circuit is well structured and easily described.    

\subsubsection{Step 1 $\exists\cdot\text{BP}\cdot\oplus\cdot\text{P}\subseteq\text{BP}\cdot\oplus\cdot\text{BP}\cdot\oplus\cdot\text{P}$}

We would like to replace an OR gate by an approximate majority gate followed by parity gates.  First, we note that  

$\exists\cdot\text{BP}\cdot\oplus\cdot\text{P}$, can be written as 

$\exists _{x},\text{BP} _{y},\oplus _{z}$,M(w,x,y,z) where w is the input to M, which is a poly time machine and x,y,z are advice strings polynomial in length with respect to w.  Next, we observe that the above can be rewritten as

$\exists _{x}$,N(w,x) where N $\in\text{BP}\cdot\oplus\cdot\text{P}$.  Finally, if we could show that this is equivalent to

$\text{BP} _{{\bar h}}\oplus _{{\bar x},{\bar b},c}N_{1}(w,{\bar h},{\bar x},{\bar b},c)$ for some $N_{1} \in \text{BP}\cdot\oplus\cdot\text{P}$, we would have the desired result.  Let ${\bar h}$ be a sequence of m hash functions, ${\bar x}$ is m non-deterministic choices for N, ${\bar b}$ is m bits, and c is a bit.  

\paragraph{} First, consider $N_{2}(w,h_{i},x_{i},b_{i})$ that accepts in the following cases:

\begin{itemize}

\item if input is all zeros, or

\item $b_{i}$=1 and N(w,$x_{i}$) accepts $h_{i}(x_{i})$=1.

\end{itemize}

Observe that if for all i, N(w,$x_{i}$) rejects, $N_{2}$ has an odd number, one, of accepting strings.  If for some i, N(w,$x_{i}$) accepts, with some non-zero polynomial, based on the hash function h,  $N_{2}$ will have an even number of accepting strings.  Thus $N_{2}$ is a parity complementer for N.  $N_{2}$ employs the concepts from the Valiant-Vazirani Theorem.  

\paragraph{} Now, consider $N_{1}(w,{\bar h},{\bar x},{\bar b},c)$ that accepts in the following cases:

\begin{itemize}

\item if input is all zeros, or

\item if c=1 and for all i $N_{2}(w,h_{i},x_{i},b_{i})$

\end{itemize}

Observe that if $N_{2}$ ever rejects then $N_{1}$ will have an odd number, one,  of accepting strings.  If $N_{2}$ always accepts, then $N_{1}$ will have an even number, two, of accepting strings.  Thus if for all i N(w,$x_{i}$) rejects, $N_{1}$ will have an even number of accepting strings, and if for some i  N(w,$x_{i}$) accepts, then with non-zero probability, $N_{1}$ will have an odd number of accepting strings. $N_{1}$ is the parity complementer of the product function of $N_{2}$

By observing the parity of $N_{1}$'s computation and using a BP gate to account for the probabilistic behavior, we can see that $N_{1} \in \text{BP}\cdot\oplus\cdot\text{P}$.  

\subsubsection{Step 2 $\text{BP}\cdot\oplus\cdot\text{BP}\cdot\oplus\cdot\text{P}\subseteq\text{BP}\cdot\text{BP}\cdot\oplus\cdot\oplus\cdot\text{P}$}

Here we want to reverse the order of a parity gate and a BP gate.  

\includegraphics[scale=0.3]{l11-figure1.eps}

{\em Figure 1 : Reversing the order of BP and parity gates}

In the initial case the possibility of error is not introduced until the last level of gates, thus the probability that any f(y,z) value is erroneous is $2^{-c}$.  Once we have made the switch in gate order, each parity gate is now receiving many inputs each one of which might have been computed erroneously.  Thus taking the union bound over the maximum number of possible inputs to a particular parity gate, we get that each f(y,z) value is erroneous with probability $2^{b}\cdot 2^{-c}=2^{b-c}$.  As long as c is much larger than b, this probability is still significantly small.  Since, we can amplify BP gates, we can ensure this property.  

\subsubsection{Step 3 $\text{BP}\cdot\text{BP}\cdot\oplus\cdot\oplus\cdot\text{P}\subseteq\text{BP}\cdot\text{BP}\cdot\oplus\cdot\text{P}$}

Here we want to eliminate one of two consecutive parity gates.  

\includegraphics[scale=0.3]{l11-figure2.eps}

{\em Figure 2 : Eliminating one of two consecutive parity gates.}

Since the sum modulo 2 of other sums modulo 2, can be accomplished on a single ``sum modulo 2'' machine, we can collapse the parity gates, with added fan-out being the only cost.  

\subsubsection{Step 4 $\text{BP}\cdot\text{BP}\cdot\oplus\cdot\text{P}\subseteq\text{BP}\cdot\oplus\cdot\text{P}$}

Here we want to eliminate one of two consecutive BP gates.  

\includegraphics[scale=0.3]{l11-figure3.eps}

{\em Figure 3 : Eliminating one of two consecutive BP gates.}

If in the first case the error of the first level BP gate is $\epsilon$ and that of the second level BP gates is $\lambda$, then by the union bound, the error of the single BP gate is $\epsilon + \lambda$.  Notice that we did not use the Razborov - Smolensky theorem because we wanted to preserve uniformity.  

We observe that most of the power of $\text{BP}\cdot\oplus\cdot\text{P}$ seems to come from the parity operator.  The ability to know whether the number of accepting strings is even or odd seems extremely powerful because this calculation is so sensitive to change.  A single string in or out of the set changes the result.  

\subsection{Part II - $\text{BP}\cdot\oplus\cdot\text{P}\subseteq\PsP$}

Consider a language $L = \text{BP} _{y}\cdot\oplus _{z}\cdot\text{L'}$, where $\text{L'}\in\text{P}$.  Using amplification on BP we can view L as:

\begin{enumerate}

\item if $x \in L$, then $Pr_{y}[|{z : L'(x,y,z) = 1}| \text{ is odd}] \geq 2/3$; and

\item if $x \not\in L$, then $Pr_{y}[|{z : L'(x,y,z) = 1}| \text{ is odd}] < 1/3$

\end{enumerate}

And in the circuit conceptualization as:

\includegraphics[scale=0.3]{l11-figure4.eps}

{\em Figure 4 : Circuit for language L}  Where N is the size of the fan out of the BP gate.

\subsubsection{Boosting parity gate}

\paragraph{} Thus by posing the question, ``for a certain x how many f(y,z)'s exist such that f(x,y,z)=1?'', we want to able to determine whether $x \in L$.  We would thus be asking the oracle for something of the form $\sum_{y}\sum_{z} L'(x,y,z)$.  The problem with our current modulo-2 parity operator is that because the sum of two odds is even we can't distinguish between cases such as,

\begin{enumerate}

\item for $y_{1}$ there are 3 accepting z's, for $y_{2}$ there are 5 accepting z's, for $y_{3}$ there are 9 accepting z's, and for $y_{4}$ there are 2 accepting z's.

\item for $y_{1}$ there are 3 accepting z's, for $y_{2}$ there are 2 accepting z's, for $y_{3}$ there are 4 accepting z's, and for $y_{4}$ there are 6 accepting z's.

\end{enumerate}

In both situation the result of the summation is 1 (mod 2).  However, in case 1 $Pr_{y}[|{z : L'(x,y,z) = 1}| \text{ is odd}] = 3/4$ and in case 2, $Pr_{y}[|{z : L'(x,y,z) = 1}| \text{ is odd}] = 1/4$.  

\paragraph{} It thus appears that if we could increase our field by having a parity operator that worked modulo-v, for some large v we could avoid this overlap of information and could correctly distinguish between the two cases based on the result of the sum.  Say we had a parity gate that operated modulo-$2^{m}$, where $2^{m} > N$, (where N is the fan out of the BP gate, maximum number of y's).  We could then see that if

\begin{itemize}

\item $x \in L$ then the sum (mod $2^{m}$) $\in [2/3 N, N]$, and

\item $x \not\in L$ then the sum (mod $2^{m}$) $\in [0 , 1/3 N]$.

\end{itemize}

If we start with a parity gate operating in modulo-K and want to boost it to a gate operating modulo-$K^{2}$, we see that the relationship is not preserved when operating in \{0,1\}, but is preserved when operating in \{0,-1\}.  This slight modification causes us to update the previous expression to:

\begin{itemize}

\item $x \in L$ then the sum (mod $2^{m}$) $\in [-2/3 N, -N]$, and

\item $x \not\in L$ then the sum (mod $2^{m}$) $\in [0 , -1/3 N]$.

\end{itemize}

\subsubsection{Arithmetic Games}

The idea of boosting parity gates motivates the use of arithmetic on the number of accepting paths in non-deterministic Turing machines.  Let $n_{1}(x)$ and $n_{2}(x)$ be the number of accepting paths of $N_{1}$ and $N_{2}$ on some input x, where $N_{1}$ and $N_{2}$ are NTM's.  

\paragraph{}{\bf Definition 1.1} $N_{+}(x)$ is an NTM such that $n_{+}(x) = n_{1}(x) + n_{2}(x)$

\paragraph{}Thus the number of accepting strings of $N_{+}$ is equal to the sum of the number of accepting strings of $n_{1}(x)$ and $n_{2}(x)$.  To see that this is plausible, construct $N_{+}(x)$ in this manner:

\paragraph{} On input w, $N_{+}$=''

\begin{enumerate}

\item non-deterministically make a choice between $N_{1}$ and $N_{2}$

\item if $N_{1}$ chosen, simulate $N_{1}$ on w.  Accept if it accepts

\item if $N_{2}$ chosen, simulate $N_{2}$ on w.  Accept if it accepts

\end{enumerate}

The running time of $N_{+}$ is the maximum of the running times of $N_{1}$ and $N_{2}$.  Consider this with circuits, $C_{1}$ and $C_{2}$, that accept $n_{1}$ and $n_{2}$ n-bit inputs respectively, we can construct $C_{+}$ to be $C_{+}(x,b) = (b \wedge C_{1}(x)) \vee (\bar{b}\wedge C_{2}(x))$, where b is a single bit.

\paragraph{}{\bf Definition 1.2} $N_{*}(x)$ is an NTM such that $n_{*}(x) = n_{1}(x) * n_{2}(x)$

\paragraph{}Thus the number of accepting strings of $N_{*}$ is equal to the product of the number of accepting strings of $n_{1}(x)$ and $n_{2}(x)$.  To see that this is plausible, construct $N_{*}(x)$ in this manner:

\paragraph{} On input w, $N_{*}$=''

\begin{enumerate}

\item simulate $N_{1}$ on w

\item if $N_{1}$ accepts, simulate $N_{2}$ on w.  Accept if $N_{2}$ accepts.

\item if $N_{1}$ rejects, reject.

\end{enumerate}

The running time of $N_{*}$ is the sum of the running times of $N_{1}$ and $N_{2}$.  Consider this with circuits, $C_{1}$ and $C_{2}$, that accept $n_{1}$ and $n_{2}$ n-bit inputs respectively, we can construct $C_{*}$ to be $C_{*}(x) =  C_{1}(x) \wedge C_{2}(x)$.

\paragraph{} Given a polynomial time NTM that has n(x) accepting paths, using $N_{+}$ and $N_{*}$ we can construct a polynomial time NTM $N_{p}(x)$ that has $P_{|x|}(n(x))$ accepting paths, where $P_{|x|}(n(x))$ is a polynomial of degree poly(n) and has positive coefficients with values at most $2^{\text{poly(n)}}$.

Now we return to the idea of boosting our parity gate.  We want to find a polynomial p that preserves the relationship:

\begin{itemize}

\item $p(x)=0$ $(mod K^{2})$ if $x=0$ $(mod K)$, and

\item $p(x)=-1$ $(mod K^{2})$ if $x=-1$ $(mod K)$.

\end{itemize}

Consider the polynomial $p(x)=3x^{4}+4x^{3}$.  It can be verified that this polynomial preserves the necessary relationship.  Try adding $a\cdot x^{2}(x+1)^{2}$ to p(x), for some integer a, and note that the values (mod K) and (mod $K^{2}$) are not effected.  Once we have this polynomial to test membership in $L = \text{BP} _{y}\cdot\oplus _{z}\cdot\text{L'}$ (defined above), we look at the sum $\sum_{y}p(\sum_{z} L'(x,y,z))$ $mod(2^{m})$.  This sum can be returned via a single query to a \#P oracle.  Thus $L \in \PsP$ and $\text{BP}\cdot\oplus\cdot\text{P}\subseteq\PsP$.

\section{Interactive Proofs}

\subsection{Background Work}

The notion of interactive proofs was defined by Goldwasser, Micali, and Rackoff (ca. 1982-1984).  The motivation for their work was cryptography.  A few years later, Babai and Moran(1988) addressed this notion from a number theoretic perspective.  

\subsection{Cryptography}

A common problem in cryptography is secure user identification.  For example, a user P wants to identify himself to a computer C, by proving to C that he knows the password X.  C might prompt P with some questions and an interaction will ensue, after which C will or will not be convinced that the party she is talking to knows the password X.  Because this interaction may take place over insecure communication channels, user P does not want to send the entire password X over the channel.  The original belief was that, ``to prove that I know X, I must show you X.''  Goldwasser addressed the formal definitions of ``knowledge'' and ``proof''.

\subsection{Introduction to Interactive Proofs}

{\em The power of a theorem proof system is modeled by the language for which it can prove membership}.   

An interactive proof consists of a verifier, V, and a prover, P.  V knows some value x and P attempts to prove to V that it also knows the value x by sending some kind of proof, $\pi$ to V.  Thus,

\begin{itemize}

\item $V(x,\pi)=\text{Accept}\rightarrow x\in L$

\item $V(x,\pi)=\text{Reject}\rightarrow \pi \text{is not a valid proof that} x \in L$

\end{itemize}

\paragraph{Definition 2.1} A verifier V is said to be complete for a language L if $\forall x \in L$  $\exists $  $\pi \text{s.t.}$  $V(x,\pi)$ accepts.

\paragraph{Definition 2.2} A verifier V is said to be sound for a language L if $\forall x \not\in L$  $\forall$ $\pi$ $V(x,\pi)$ rejects.

\paragraph{} In the interaction, V is assumed to be a polynomial time machine, while P is an infinitely powerful one.    The interaction starts by P sending something to V to let V know that P wants to prove something about x.  V responds with $q_{1}=q(x)$, a question about x.  P responds with $a_{1}=a(x,q_{1})$, an answer based on what he is trying to prove and the verifier's question.  V then responds with $q_{2}=q(x,a_{1})$.  The interaction continues in this manner until P sends the final answer to V.  At this point V either rejects or accepts.  All of the functions q, as well as the final decision, computed by V, must be computed in polynomial time.  

\paragraph{} {\bf If P is infinitely powerful and V is a polynomial machine, why is interaction useful?  Can't P just compute the entire interaction ahead of time?}  In the model outlined above this indeed appears to be the case.  The power of interaction is apparent when V is allowed to have randomness.  In the interaction above, V is now also allowed to flip coins and send random strings to P as part of its questions.  The definitions of completeness and soundness are modified for a random polynomial time verifier.  

\paragraph{Definition 2.3} A verifier V with randomness is said to be complete for a language L if $\forall x \in L$  $\exists$ a prover that convinces V that x $\in L$ with probability $\geq 2/3$

\paragraph{Definition 2.4} A verifier V is said to be sound for a language L if $\forall x \not\in L$ and $\forall$ provers, V accepts P's proof with probability $< 1/3$ 

\paragraph{}  Because of its power of randomness, V might not necessarily know whether x $\in L$.  However, by repeatedly asking P certain questions and observing that the same random strings always produce the same answer V will be convinced that P indeed knows that x $\in L$.  For example, the invisible chalk on paper game.  

\paragraph{} We will continue the discussion of Interactive Proofs in the next lecture.

\end{document}