\documentclass{article}
\usepackage{amsfonts, amssymb, amsmath}
\input{macros}
\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{\upath}{\text{\sc{UndirectedPath}}}


\begin{document}
\header{6.841/18.405J Advanced Complexity Theory}{February 26, 2003}
{6: Randomized Algorithms, Properties of $\BPP$}
{Prof. Madhu Sudan}{Shien Jin Ong}


\noindent {\bf Recap:}
In the previous lecture, we defined $\ZPP, \RP, \coRP, \BPP$.
The following relationships between complexity classes are known.
\begin{enumerate} 
\item $\P \subseteq \ZPP \subseteq \RP \subseteq \NP$
\item $\P \subseteq \ZPP \subseteq \coRP \subseteq \coNP$.
\item $\RP \cup \coRP \subseteq \BPP$.
\item $\ZPP = \RP \cap \coRP$.
\end{enumerate}
%
The relationship between $\BPP$ and $\NP$ is still
unknown. We, however, can prove that $\P = \BPP$ under some reasonable
assumptions. Therefore, our belief is that $\P = \BPP \subseteq \NP$.

\section{Examples of Randomized Algorithms}

We give randomized algorithms for the following problems.
%
\begin{enumerate}
\item Polynomial Identity Testing.
\item Undirected Path.
\end{enumerate}

\subsection{Polynomial Identity Testing}

We study the polynomial identity testing in the oracle model. That is
given two multivariate polynomial $p(x_1, \dots, x_n)$ and $q(x_1,
\dots, x_n)$ over a field $\F$, can we determine that $p = q$? This
problem is equivalent to determining whether $h \eqdef p - q = 0$. We assume
that the polynomial $h$ is not given to us explicitly, but as an
oracle $O_h$ (black box). Given inputs $\al_1, \dots, \al_n \in \F$, 
oracle $O_h$ will output the value of $h(\al_1, \dots, \al_n)$.

Next, we define the \emph{total degree} of a polynomial.
Let $p$ be a polynomial such that
\[ p(x_1, \dots, x_n) = \sum c_{i_1 \cdots i_n} x_1^{i_1} \cdots
x_n^{i_n}. \]
%
Then,
\[ \text{total degree of } p = \max_{c_{i_1 \cdots i_n} \neq 0} \{ i_1 + \dots + i_n \}. \]


\noindent {\bf Problem} (Polynomial Identity Testing): 
Given oracle $O_h$ which computes the polynomial $h$ of total degree
$d$ in $n$ variables over a finite field $\F$. 
Does there exist $\al_1, \dots, \al_n \in \F$ such that 
$h(\al_1,\dots, \al_n) \neq 0$, \ie is $h(x_1, \dots, x_n) \neq 0$?

Trivially, polynomial identity testing (PIT) can be done in $\NP^A$
(nondeterministic polynomial time in $n$, $d$, and $\abs{F}$).
However, PIT is not in $\P^A$ (exercise).
%
We show that PIT is in $\RP^A$. Our randomized algorithm takes a
sufficiently large subset, $S$, of $\F$ and then choose $\al_1, \dots,
\al_n$ uniformly at random from $S$ and test whether $h(\al_1, \dots,
\al_n) = 0$.

\begin{lemma} \label{lem:sz}
If $p(x_1, \dots, x_n) \neq 0$ is a polynomial of total degree $d$ over
a field $\F$ and $S \subseteq \F$, then
\[  \Pr_{(\al_1, \dots, \al_n) \from S^n} [p(\al_1, \dots, \al_n) = 0] \leq
\frac{d}{\abs{S}}. \]
\end{lemma}

The proof of Lemma~\ref{lem:sz} is left as an exercise.
If we choose a set $S \subseteq \F$ such that $\abs{S} = 2d$, our algorithm
makes an error on instances $h(x_1, \dots, x_n) \neq 0$
with probability at most $1/2$. When $h(x_1, \dots, x_n) = 0$, our
algorithm never errs.

Let us do an example to illustrate the appplicability of
Lemma~\ref{lem:sz}.

{\bf Problem 1:} What is the probability (over $x_1, \dots, x_n$) 
that $x_1 \xor x_3 \xor x_n =0$? 

{\bf Answer:} Since the operation $\xor$ is just addition modulo 2, 
the probability is at most $1/2$
(in fact, exactly $1/2$).

{\bf Problem 2:} Suppose we are given a $n \times n$ matrix $M$ whose
entries are linear equations of $x_1, \dots, x_k$. Can
we decide whether $\det(M) \equiv 0$? 

{\bf Answer:} Since $\det(M)$ can be evaluate efficiently when we plug
in values for $x_1, \dots, x_k$, this problem is in $\RP$.

%----------------------------------------------------------------------

\subsection{Undirected Path}

Analogous with the randomized time complexity classes, we have the
following randomized log-space complexity classes -- $\ZPL, \RP, \coRL,
\BPL$.
%
There are two major differences between a randomized log-space machine
and a randomized polynomial-time machine.

\begin{enumerate}
\item For randomized log-space computations, we require that the
  machine has only one-way access to the random tape. 
This means that the log-space machine cannot see
the previous random bits unless it has stored the random bits on its work tape
tape.
\item The randomized log-space machine must halt in
polynomial-time. If this requirement were to be waived, 
directed path can be solved in randomized log-space.
\end{enumerate}

Define the undirected path problem as follows.
%
\[ \upath = \{ \ip{G, s, t} : \text{$G$ is an undirected graph and there
  exists a path from $s$ to $t$.} \} \]
%
Is $\upath \in \LOG$? While this problem is still open, we know that
$\upath \in \NL \subseteq \LOG^2$.
%
Aleliunas, Karp, Lipton, Lovasz, and Rackoff showed that $\upath \in
\RL$. The randomized logspace algorithm is just the algorithm which
does a random walk on the graph $G$.

\vspace{0.1in}

\noindent {\bf Randomized Logspace Algorithm for $\upath$}

\noindent On input $(G, s, t)$, do the following.
\begin{enumerate}
\item \texttt{current} $\from s$.
%
\item for $i = 1$ to $O(V(G)^3)$
  \begin{enumerate}
    \item Pick a random neighbor $v$ of the current vertex and set
          \texttt{current} $\from v$.
    \item If \texttt{current} $= t$, halt and \emph{accept}.
  \end{enumerate}
%
\item If we have not reached $t$ after $O(V(G)^3)$ steps, \emph{reject}.
\end{enumerate}

The correctness of the above algorithm is based on the following lemma.

\begin{lemma}
Let $G$ be a connected, undirected graph on $n = V(G)$ vertices.
Then, we have that
\[ \Pr[\text{walk of length $O(n^3)$ does not visit all vertices}]
\leq \frac{1}{2} \]
\end{lemma}


Considering that $\upath \in \RL$, can $\upath$ be solved in less than
$(\log n)^2$ space?
%
Thus far, we know that $\upath \in \LOG^{4/3}$ and  $\RL \subseteq \LOG^{3/2}$.


\section{$\BPP$ has polynomial-sized circuits}

Recall that $\Ppoly$ is the class of languages decidable by
polynomial-sized circuits.
%
Previously, we defined the class $\BPP$ as follows.

A language $L \in \BPP$ if there exist a probabilistic polynomial-time
algorithm $M$ such that 
%
\begin{eqnarray*}
x \in L & \implies & \Pr_r[M(x, r) = 1] \geq 2/3. \\
x \notin L & \implies & \Pr_r[M(x, r) = 1] \leq 1/3.
\end{eqnarray*}

The error bound in such $\BPP$-algorithm is $1/3$.
To prove that $\BPP \subset \Ppoly$, we need to amplify the confidence
(make the error bound exponentially small).

We achieve this by repeating our $\BPP$-algorithm 
    $\poly(\abs{x})$ times and taking majority vote. 
Using the Chernoff bound analysis, our error is reduced to
$2^{-2\abs{x}}$.
Hence, an alternative formulation of $\BPP$  follows.

A language $L \in \BPP$ if there exist a probabilistic polynomial-time
algorithm $M$ such that 
%
\begin{eqnarray*}
x \in L & \implies & \Pr_r[M(x, r) = 1] \geq 1 - 2^{-2\abs{x}}.\\
x \notin L & \implies & \Pr_r[M(x, r) = 1] \leq 2^{-2\abs{x}}.
\end{eqnarray*}

\begin{theorem}{(Adelman)}
$\BPP \subset \Ppoly$.
\end{theorem}

\begin{proof}
Fix a language $L \in \BPP$ and let $M$ be a $\BPP$-algorithm for $L$
with error bound $2^{-2\abs{x}}$.
Let $\chi_L$ be the characteristic
function for $L$, \ie $\chi_L(x) = 1$ if $x \in L$, and $\chi_L(x) =
0$ if $x \notin L$. 
For each $x$ of length $n$, define $r$ to be \emph{bad} for $x$ if
$M(x, r) \neq \chi_L(x)$.

We know that for any $x \in \zo^n$,
\[ \Pr_r[\text{$r$ is bad for $x$}] \leq  2^{-2n}. \]
%
By the union bound, we have
\[ \Pr_r[\text{$r$ is bad for any $x \in \zo^n$}] \leq  2^n 2^{-2n} =
2^{-n}. \]
%
Hence, there exists an $r^*$ that is good for all $x \in \zo^n$. This
means that $M(x, r^*) = \chi_L(x)$ for all $x \in \zo^n$. In addition,
$\abs{r^*} = \poly(n)$.
%
The string $r^*$ will be the nonuniform advice for
deciding the language $L$. This shows that $L \in \Ppoly$.
\end{proof}

\end{document}