
\documentclass[10pt]{article}
\usepackage{amsfonts,amsmath,amssymb}
\usepackage{pstricks}
\usepackage{pstricks-add}
\usepackage{geometry}

\newcommand{\Set}[1]{\left\{ #1 \right\}}
\newcommand{\st}{\medspace | \medspace}
\renewcommand{\epsilon}{\varepsilon}
\newcommand{\xor}{\oplus}
\newcommand{\powerset}{\mathcal{P}}
\newcommand{\dollar}{\ensuremath{\mathdollar}}
\newcommand{\reject}{\ensuremath{\text{\textbf{reject}}}}
\newcommand{\accept}{\ensuremath{\text{\textbf{accept}}}}
\newcommand{\NTIME}{\mathrm{NTIME}}
\newcommand{\TIME}{\mathrm{TIME}}
\newcommand{\DET}{\mathrm{det}}
\newcommand{\NS}{\mathrm{NSPACE}}
\newcommand{\SP}{\mathrm{SPACE}}
\newcommand{\NP}{\mathrm{NP}}
\newcommand{\BPP}{\mathrm{BPP}}
\newcommand{\AC}[1]{\ensuremath{\mathrm{AC}^{#1}}}
\newcommand{\NC}[1]{\ensuremath{\mathrm{NC}^{#1}}}
\newcommand{\Piyes}{\Pi_{\mathrm{YES}}}
\newcommand{\Pino}{\Pi_{\mathrm{NO}}}
\newcommand{\Ppoly}{\mathrm{P}/\mathrm{poly}}
\newcommand{\Poly}{\mathrm{P}}
\newcommand{\HALT}{\mathrm{HALT}}
\newcommand{\Lhalt}{L_{\HALT}}
\renewcommand{\phi}{\varphi}
\newcommand{\SAT}{\mathrm{SAT}}
\DeclareMathOperator{\balance}{balance}
\DeclareMathOperator{\maj}{maj}
\newcommand{\num}[1]{\#_{#1}}
\newcommand{\MUX}{\text{MUX}}
\newcommand{\BPexists}[1]{\mathrm{BP}\cdot\exists\cdot{#1}}
\newcommand{\existsBPP}{\exists\cdot\mathrm{BP}\cdot\mathrm{P}}
\newcommand{\BPexistsP}{\mathrm{BP}\cdot\exists\cdot\mathrm{P}}
\newcommand{\prRP}{\mathrm{prRP}}
\newcommand{\prcoRP}{\mathrm{prCoRP}}
\newcommand{\prBPP}{\mathrm{prBPP}}
\newcommand{\IP}{\mathrm{IP}}
\newcommand{\AM}{\mathrm{AM}}
\newcommand{\GNI}{\mathrm{GNI}}
\DeclareMathOperator{\perm}{perm}

\psset{unit=2.1pt}
\psset{dotsize=2pt 5}


\begin{document}
\input{preamble.tex}

\lecture{15}{April 1, 2009}{Madhu Sudan}{Rotem Oshman}

\section{Today's topics}
\begin{itemize}
	\item Private coins $\equiv$ public coins (that is, $\IP[k] \equiv \AM$)
		\begin{itemize}
			\item Goldwasser-Sipser approximate counting protocol
		\end{itemize}
	\item Towards protocols for the Permanent, in the goal of showing that $\#\Poly \subseteq \IP$.
\end{itemize}

\section{Review of last lecture}
\subsection{Graph Non-Isomorphism}
The graph non-isomorphism problem is to decide the language $\GNI = \set{ (G_0, G_1) \st G_0 \not \sim G_1}$. Last lecture we saw a private-coin 2-round protocol for GNI:
\begin{itemize}
	\item The Verifier chooses a permutation $\pi \in_R S_n$, where $n$ is the number of nodes in the graph, and a bit $b \in_R \set{0,1}$. It sends $H = \pi(G_b)$ to the Prover.
	\item The Prover returns with a bit $b'$.
	\item The Verifier accepts if $b = b'$.
\end{itemize}
If $G_0 \sim G_1$, then the bit $b$ is independent of $H$, which means that the Prover is essentially guessing $b'$ and has a probability of $1/2$ of being correct. If $G_0 \not \sim G_1$, then $H$ identifies $b$ uniquely and the Prover will always be correct.
\subsection{Kilian's protocol: $\IP[k] \subseteq \AM[\mathrm{poly}]$}
Last time we saw a public-coin protocol through which the Prover could convince the Verifier that there are ``many'' coin tosses that would have made the Verifier accept in the original \emph{private-coin} protocol. Kilian's protocol is public coin and has completeness of 1, but the number of rounds in the protocol depends on the number of random coins used in the original private-coin protocol. For example, the public-coin protocol we would get for GNI would have $O(n \log n)$ rounds instead of 2.

\section{The Goldwasser-Sipser Protocol}
Let $S \subseteq \set{0,1}^n$ be a set, such that membership in $S$ is verifiable in $\AM$. We are interested in solving the promise problem given by
\begin{align*}
	& \Piyes = \set{ S : |S| \geq f(n) } \\
	& \Pino = \set{ S : |S| < \frac{f(n)}{10n^2}}
\end{align*}
\subsection{Initial attempt}
Suppose that $f(n)$ is ``very large'': $f(n) \approx 2^n$ (actually a little less than that). In this case, for YES instances we have $\frac{|S|}{|\set{0,1}^n|} \approx 1$, and for NO instances we have $\frac{|S|}{|\set{0,1}^n|} \stackrel{<}{\sim} \frac{1}{n^2}$. In other words, when we choose a random string, for YES instances our chance of hitting a member of $S$ is very high, and for NO instances it is about $1$ in $n^2$. We can re-use ideas from the proof that $\BPP \subseteq \Sigma_2^{\Poly}$ to convince the Verifier that $|S| \geq f(n)$. The protocol would be as follows.
\begin{center}
\pspicture(-40,-15)(120,88)
\psframe(-40,-15)(120,88)
\uput{2.5}[l](0,80){\underline{Verifier}}
\uput{2.5}[r](80,80){\underline{Prover}}

\psline[arrowsize=2 3]{<-}(0,70)(80,70)
\uput{1}[u](40,70){$x_1, \ldots, x_k \in \set{0,1}^n$}

\psline[arrowsize=2 3]{->}(0,55)(80,55)
\uput{1}[u](40,55){$x \in_R \set{0,1}^n$}

\psline[arrowsize=2 3]{<-}(0,40)(80,40)
\uput{1}[u](40,40){$i : x_i \xor x \in S$}

\psline[arrowsize=2 3]{->}(0,25)(80,25)
\uput{1}[u](40,25){Query}
\psline[arrowsize=2 3]{<-}(0,10)(80,10)
\uput{1}[u](40,10){Response}

\psbrace[ref=rC,rot=180,nodesepA=-3](-3,27)(-3,8){\parbox{1.7cm}{Verify that $x_i \xor x \in S$ }}

\uput{1}[l](40,-5){\parbox{5cm}{Verifier accepts iff it is ``convinced'' that $x_i \xor x \in S$.}}

\endpspicture
\end{center}
\noindent
Unfortunately, this only works when $f(n) \approx \frac{2^n}{\text{poly}}$.

\subsection{Using hasing to overcome small $f(n)$'s}
We can use pairwise-independent hashing to map $S$ to a smaller space $\set{0,1}^m$, so that if $S$ is large, then $h(S)$ will be a very large fraction of $\set{0,1}^m$. If $h$ is a hash function that has no collisions in $S$ then $|h(S)| = |S|$; therefore, if we choose $m \approx \log f(n)$ and $S$ is a YES instance ($|S| \geq f(n)$), then in the hash-space we will have $|h(S)| = |S| \approx 2^m$. Then we can execute the previous protocol in the hash-space:

\begin{center}
\pspicture(-40,-15)(120,100)
\psframe(-40,-15)(120,100)
\uput{2.5}[l](0,90){\underline{Verifier}}
\uput{2.5}[r](80,90){\underline{Prover}}

\psline[arrowsize=2 3]{->}(0,85)(80,85)
\uput{1}[u](40,85){$h \in_R \mathcal{H}$}

\psline[arrowsize=2 3]{<-}(0,70)(80,70)
\uput{1}[u](40,70){$x_1, \ldots, x_k \in \set{0,1}^m$}

\psline[arrowsize=2 3]{->}(0,55)(80,55)
\uput{1}[u](40,55){$x \in_R \set{0,1}^m$}

\psline[arrowsize=2 3]{<-}(0,40)(80,40)
\uput{1}[u](40,40){$i,y : y \in S \text{ and } h(y) = x_i \xor x$}

\psline[arrowsize=2 3]{->}(0,25)(80,25)
\uput{1}[u](40,25){Query}
\psline[arrowsize=2 3]{<-}(0,10)(80,10)
\uput{1}[u](40,10){Response}

\psbrace[ref=rC,rot=180,nodesepA=-3](-3,27)(-3,8){\parbox{1.7cm}{Verify that $y \in S$ }}

\uput{1}[l](40,-5){\parbox{5cm}{Verifier accepts iff $h(y) = x_i \xor x$ and it is ``convinced'' that $y \in S$.}}

\endpspicture
\end{center}
\noindent
where $\mathcal{H}$ is a pairwise-independent family of hash functions.

The problem with \emph{this} is that $h(S)$ is only guaranteed to be large if $h$ has no (or few) collisions in $S$; if $h(S)$ is too small we have the same problem we had when $f(n)$ was small --- the prover may not have a good response $x_1, \ldots, x_k$ in the second round.

To decrease the chances of this bad event we will use more than one hash function, so that the probability that \emph{one} of the hash functions is good will be very high. We need to make sure that if $S$ is small (a NO instance), our multiple hash functions will not give the Prover too much freedom by mapping $S$ to a large fraction of $\set{0,1}^m$.

\subsection{Final protocol}
Let $m = \log f(n) + 2$. The protocol is as follows.

\begin{center}
\pspicture(-40,-15)(120,100)
\psframe(-40,-15)(120,100)
\uput{2.5}[l](0,90){\underline{Verifier}}
\uput{2.5}[r](80,90){\underline{Prover}}

\psline[arrowsize=2 3]{->}(0,85)(80,85)
\uput{1}[u](40,85){$h_1,\ldots,h_m \in_R \mathcal{H}$}

\psline[arrowsize=2 3]{<-}(0,70)(80,70)
\uput{1}[u](40,70){$x_1, \ldots, x_k \in \set{0,1}^m$}

\psline[arrowsize=2 3]{->}(0,55)(80,55)
\uput{1}[u](40,55){$x \in_R \set{0,1}^m$}

\psline[arrowsize=2 3]{<-}(0,40)(80,40)
\uput{1}[u](40,40){$i,j,y : y \in S \text{ and } h_j(y) = x_i \xor x$}

\psline[arrowsize=2 3]{->}(0,25)(80,25)
\uput{1}[u](40,25){Query}
\psline[arrowsize=2 3]{<-}(0,10)(80,10)
\uput{1}[u](40,10){Response}

\psbrace[ref=rC,rot=180,nodesepA=-3](-3,27)(-3,8){\parbox{1.7cm}{Verify that $y \in S$ }}

\uput{1}[l](40,-5){\parbox{5cm}{Verifier accepts iff $h_j(y) = x_i \xor x$ and it is ``convinced'' that $y \in S$.}}

\endpspicture
\end{center}
\noindent

\subsubsection{Analysis}
First suppose that $S$ is a NO instance, that is, $|S| < \frac{f(n)}{10n^2}$. Then
\begin{align*}
	\frac{|\bigcup_j h_j(S)|}{|\set{0,1}^m|} \leq \frac{m \cdot |S|}{2^m} < \frac{(\log f(n) + 2)\cdot f(n)}{10n^2\cdot4f(n)} \leq \frac{1}{20n}
\end{align*}
(In the last step we used the fact that $2 \leq f(n) \leq 2^n$, otherwise the problem definition does not make sense). It follows that for NO instances, for every choice of $x_1, \ldots, x_n$ that the Prover may send, the Verifier has a high probability of selecting a string $x$ such that for all $i$, $x_i \xor x \not \in \bigcup_j h_j(S)$. The Prover will not have a response $i, j, y$ that has a high probability of making the Verifier accept.

Now suppose that $S$ is a YES instance, that is, $|S| \geq f(n)$. We are interested in the probability of choosing $h_1,\ldots,h_m$ such that for some $j \in \set{1,\ldots,m}$ we have $|h_j(S)| \geq f(n)$. This ensures that the Prover has a response in the second round.

Since each $\mathcal{H}$ is pairwise-independent, for any fixed $x \neq y \in \set{0,1}^n$ and for every $a,b \in \set{0,1}^m$ we have
\begin{equation*}
	\Pr_{h \in \mathcal{H}} \left[ h(x) = a \land h(y) = b  \right] = \frac{1}{4^{m}}
\end{equation*}
and hence,
\begin{equation*}
	\Pr_{h \in \mathcal{H}} \left[ h(x) = h(y) \right] = \sum_{a \in \set{0,1}^m} \Pr_{h \in \mathcal{H}} \left[ h(x) = a \land h(y) = a \right] \leq 2^m \cdot \frac{1}{4^m} = \frac{1}{2^m}
\end{equation*}
Let $S' \subseteq S$ be some subset of size $f(n)$ of $S$ (recall that $|S| \geq f(n)$). By a union bound over elements of $S'$ (``unfixing'' $y$) we obtain
\begin{equation*}
	\Pr_{h \in \mathcal{H}} \left[ \exists y \in S' : x \neq y \land h(x) = h(y) \right] \leq \frac{f(n)}{2^m} = \frac{f(n)}{4f(n)} = \frac{1}{4}
\end{equation*}
Therefore,
\begin{equation*}
	\Pr_{h_1, \ldots, h_m \in \mathcal{H}} \left[ \forall j \exists y \in S' : x \neq y \land h_j(x) = h_j(y) \right] \leq \frac{1}{4^m}
\end{equation*}
Finally, by another union bound over the elements of $S'$ (``unfixing'' $x$ this time),
\begin{equation*}
	\Pr_{h_1, \ldots, h_m \in \mathcal{H}} \left[ \exists x \in S' \forall j \exists y \in S' : x \neq y \land h_j(x) = h_j(y) \right] \leq \frac{f(n)}{4^m} = \frac{f(n)}{8f^(n)} < \frac{1}{f(n)}
\end{equation*}
It follows that with probability all but $1/f(n)$, every element of $S'$ is mapped without collision by some $h_j$, which implies $|\bigcup_j h_j(S)| \geq |S'| = f(n)$. This is sufficient to use the $\BPP \subseteq \Sigma_2^{\Poly}$-style protocol above.

\section{$\IP[2] \subseteq \AM$}
We will use the Goldwasser-Sipser approximate counting protocol to convert a 2-round private coin protocol into a constant-round public-coin protocol. Since $\AM[k] = \AM$ for any constant $k$ (see problem set \#3), this will show that $\IP[2] \subseteq \AM$.

A 2-round private-coin protocol looks like this:

\begin{center}
\pspicture(-40,5)(120,100)
\psframe(-40,5)(120,100)
\uput{2.5}[l](0,90){\underline{Verifier}}
\uput{2.5}[r](80,90){\underline{Prover}}

\uput{2.5}[u](-8,70){\parbox{2.5cm}{Chooses\\ $R \in_R \set{0,1}^{r(n)}$}}

\psline[arrowsize=2 3]{->}(0,60)(80,60)
\uput{1}[u](40,60){$q = q(R)$}

\psline[arrowsize=2 3]{<-}(0,45)(80,45)
\uput{1}[u](40,45){$a$}

\uput{2.5}[u](-8,15){\parbox{2.5cm}{Verifier checks that $(R, q, a)$ is acceptable}}

\endpspicture
\end{center}
\noindent
Define $S_{q,a} = \set{R \st (R, q, a) \text{ is acceptable}}$. If we make the simplifying assumption that there is some number $N$ such that
\begin{enumerate}
	\item In YES instances, $\forall q \exists a : |S_{q,a}| \geq N$, and
	\item In NO instances, $\forall q \forall a : |S_{q,a}| < \frac{N}{10n^2}$, and
	\item $N$ is \emph{known to the Verifier},
\end{enumerate}
then the Prover could convince the Verifier that it should accept by sending a pair $(q,a)$ that it claims has $|S_{q,a}| \geq N$, and then the Verifier and the Prover would run the GS protocol to verify that $|S_{q,a}| \geq N$. However, in reality, $N$ is not known to the verifier, and furthermore $N$ can depend on $q$ (that is, $N = N(q)$).

The solution is to have the Prover provide a number $N$ in the first round that it claims satisfies $|Q_N| \geq \frac{2}{3}\epsilon\cdot\frac{2^n}{N}$, where $\epsilon$ is some constant and where $Q_N = \set{q \st \exists a : |S_{q,a}| > N}$. That is, the prover provides a number $N$ such that ``many'' queries $q$ have an answer $a$ with $|S_{q,a}| > N$. Then the Verifier and Prover execute the GS protocol to verify the size of $Q_N$. After this, $N$ is used in the protocol from before.


\section{Properties of the Permanent}
Recall that $\perm(A) = \sum_{\sigma} \prod_{i = 1}^n A_{i, \sigma(i)}$, where $A \in \mathbb{Z}_p^{n \times n}$.

\begin{itemize}
	\item \textbf{Random self-reducibility:} for fixed $A, R \in \mathbb{Z}_p^{n \times n}$, let $p(i) = \perm(A + i \cdot R)$. This is a degree-$n$ polynomial in $i$. For $i = 0$ we have $p(i) = \perm(A)$.
		
		Suppose that we have an algorithm $M$ that computes $\perm(R)$ with probability $1 - \epsilon$ for random matrices $R$. Since $\mathbb{Z}_p$ is a field, for $i \neq 0$ and randomly chosen $R$, $A + i \cdot R$ is also distributed uniformly. Therefore,
		\begin{equation*}
			\Pr\left[ M(A + i \cdot R) = \perm(A + i \cdot R) \right] \geq 1 - \epsilon.
		\end{equation*}
		It follows that
		\begin{equation*}
			\Pr\left[ \forall i \in \set{1,\ldots, n} : M(A + i \cdot R) = \perm(A + i \cdot R)\right] \geq 1 - n \cdot \epsilon,
		\end{equation*}
		that is, we can compute w.h.p.\ the values $p(1), \ldots, p(n)$. These values can be used to interpolate $p$ (which is of degree $n$) and compute $p(0) = \perm(A)$.

	\item \textbf{Downward self-reducibility:} suppose we have an algorithm $M$ that computes $\perm(B)$ for $B \in \mathbb{Z}_p^{n-1 \times n - 1}$ (a smaller matrix). For an $n$-by-$n$ matrix $A$, we can write $\perm(A) = \sum_{i = 1}^n \left( a_{1,i} \cdot \perm(A \setminus i) \right)$, where $A \setminus i$ is the matrix obtained from $A$ by removing the first row and the $i$-th column. Thus, we can compute $\perm(A)$ using $n$ calls to $M(B)$, and if $M$ terminates in polynomial time then so will the computation of $\perm(A)$.
\end{itemize}

These two properties are used in an alternating manner in an interactive proof for the Permanent problem.






\end{document}

