\documentstyle[epsf]{article}
\input{Anna-preamble.tex}
\font\fiverm=cmr5
%\usepackage{amstex}
%\input pictex small.pictex
%\input latexpicobjs
%\input piclatex
%\input xypic
%\input plain
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                       BEGINING OF PREAMBLE                            %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% If you need a new command add it here and put your name next to it.
% Before you start scribing, you should look at the macros below and
% use them. We are trying to make the notes consistent.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
\newcommand{\mbf}[1]{\mbox{\bf{#1}}}
 
% Big O, small o (Andrej)
%\newcommand{\bigO}{{\mathop{\rm O}}}
\newcommand{\smallo}{{\mathop{\rm o}}}
 
% Complexity classes
\newcommand{\logspace}{\mbf{L}}     % logarithmic space (Andrej)
\newcommand{\polytime}{\mbf{P}}     % polynomial time (Andrej)
\newcommand{\EXP}{\mbf{EXP}}        % exponential time (Andrej)
\newcommand{\PP}{\mbf{PP}}
\newcommand{\PSPACE}{\mbf{PSPACE}}
\newcommand{\SPACE}{\mbf{SPACE}}
\newcommand{\FSPACE}{\mbf{FSPACE}}
\newcommand{\TIME}{\mbf{TIME}}
\newcommand{\FTIME}{\mbf{FTIME}}
\newcommand{\ACZ}{\mbf{AC}^0}
\newcommand{\RL}{\mbf{RL}}		% randomized logspace (Sasha)
\newcommand{\SC}{\mbf{SC}}		% Steve's class (Sasha)
\newcommand{\ZPP}{\mbf{ZPP}}
\newcommand{\IP}{\mbf{IP}}           % interactive proofs (Goran)
\newcommand{\AM}{\mbf{AM}}           % Arthur-Merlin proofs
\newcommand{\NPpoly}{\mbf{NP/poly}}  % NP/poly 
\newcommand{\Ppoly}{\mbf{P/poly}}    % P/poly 
\newcommand{\PH}{\mbf{PH}}           % the Hierarchy 
\newcommand{\NP}{\mbf{NP}}           % NP
\newcommand{\coNP}{\mbf{coNP}}
\newcommand{\IPMACH}{\mbf{IP-Machine}}
\newcommand{\BPP}{\mbf{BPP}}
\newcommand{\RP}{\mbf{RP}}
\newcommand{\coRP}{\mbf{coRP}}

% Communication complexity (Andrej)
\newcommand{\cost}{\mbf{COST}}
 
% Turing Machines
\newcommand{\qstart}{\mbox{$q_{start}$}}
\newcommand{\qaccept}{\mbox{$q_{accept}$}}
\newcommand{\qreject}{\mbox{$q_{reject}$}}
\newcommand{\blank}{\mbox{$\Box$}}
 
% New & Improved number sets (Andrej).
\font\sf=cmss10
\newcommand{\Nats}{{\hbox{\sf I\kern-.13em\hbox{N}}}}   % Natural numbers
\newcommand{\Reals}{{\hbox{\sf I\kern-.14em\hbox{R}}}}  % Real numbers
\newcommand{\Ints}{{\hbox{\sf Z\kern-.43emZ}}}          % Integers
\newcommand{\CC}{{\hbox{\sf C\kern -.48emC}}}           % Complex numbers
\newcommand{\QQ}{{\hbox{\sf C\kern -.48emQ}}}           % Rational numbers
 
%Macros for describing sets and functions (Andrej)
%
% It is *bad* to write $f: A \to B$, because that ':' doesn't come out right.
% Use $f \cc A \to B$ instead. (Andrej)
%
\newcommand{\cc}{\colon\thinspace}
%
% When you describe a set, like {f(x) | x < 10}, you shouldn't
% write $\{ f(x) | x < 10 \}$ becuase that won't put enough space around |.
% Use $\{f(x) \such x < 10 \}$ instead. (Andrej)
%
\newcommand{\such}{\;|\;}
 
%Logical operators (Andrej)
%\newcommand{\AND}{\land}
\newcommand{\OR}{\lor}
\newcommand{\NOT}{\neg}
\newcommand{\EQUIV}{\;\Longleftrightarrow\;}
\newcommand{\IMPLY}{\;\Longrightarrow\;}
%more logical operators (Goran)
\newcommand{\XOR}{\oplus}
\newcommand{\MAX} {\mbf {Max}}
\newcommand {\COIN} {\mbf {Coin Flip}}
%Other operators
%\newcommand{\mod}{\;{\rm mod}\;}
 
% Sasha
\newcommand{\GF}{{\mathop{\rm GF}}}
\newcommand{\sub}[1]{\mbox{$_{#1}$}}
\newcommand{\cat}{\circ}
\newcommand{\trans}[1]{\stackrel{_{#1}}{\rightarrow}}
\newcommand{\Lone}{$L_1\,$}
 
% Goran
\newcommand{\E}{{\mathop{\rm E}}}
\newcommand{\NONISO}{{\mbf{NONISO}}}
\newcommand{\ISOg}{{\mbf{ISO}}}
\newcommand{\AUTOg}{{\rm AUTO}}
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Theorems are environments with numbering schemes
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
%\newtheorem{theorem}{Theorem}[section]
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{corollary}[theorem]{Corollary}
%\newtheorem{definition}{Definition}[section]
%\newtheorem{fact}{Fact}
%\newtheorem{assumption}{Assumption}
 
%\newenvironment{proof}{\QuadSpace\par\noindent{\bf Proof}:}{\EndProof\HalfSpace}
%\newenvironment{proofsketch}{\QuadSpace\par\noindent{\bf Proof sketch}:}{\EndProof\HalfSpace}
%\newenvironment{notation}{\QuadSpace\par\noindent{\bf Notation}:}{\HalfSpace}
%\newenvironment{intuition}{\begin{quote}\par\noindent{\bf Intuition}:}{\end{quote}}
%\newenvironment{note}{\QuadSpace\par\noindent{\bf Note}:}{\HalfSpace}
%\newenvironment{convention}{\QuadSpace\par\noindent{\bf Convention}:}{\HalfSpace}
%\newenvironment{example}{\QuadSpace\par\noindent{\bf Example}:}{\HalfSpace}
%\newenvironment{question}{\QuadSpace\par\noindent{\bf Question}:}{\HalfSpace}
%\newenvironment{remark}{\QuadSpace\par\noindent{\bf Remark}:}{\HalfSpace}
%\newenvironment{observation}{\QuadSpace\par\noindent{\bf Observation}:}{\HalfSpace}
%\newenvironment{proposition}{\QuadSpace\par\noindent{\bf Proposition}:}{\HalfSpace}
 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%       DO NOT EVEN THINK OF CHANGING THE PREAMBLE BELOW HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

 
\begin{document}
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%               UDPATE the header and synopsis below                    %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%The \lecture command takes 5 arguments as follows:
% \lecture{lecture number}{date of lecture}{lecturer (me usually)}{name of scribe (YOU)}{title of lecture}
 
\lecture{8}{March 5, 1998}{Madhu Sudan}{Anna Lysyanskaya}
 
% Each lecture should have a synopsis.
%\begin{quote} {\bf Synopsis:}
%$\BPP \  , \RP,$ Read Once Branching Programs, Schwarz's lemma
%\end{quote}
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%               Place body of SCRIBE notes after here                   %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
%               Brilliant and clear notes go here
\section{Amplification of \BPP \  }
Recall that in the last lecture we viewed \BPP \   as the class of languages 
for which there exists a probabilistic polynomial time Turing machine
such that:
\begin{itemize}
\item for all strings in the language, the machine will accept with 
probability at least $\frac{2}{3}$;
\item for all strings not in the language, the machine will accept with 
probability at most $\frac{1}{3}$.
\end{itemize}
Now we are going to 
present a more broad definition of \BPP. Instead of fixed 
constants $\frac{2}{3}$ and $\frac{1}{3}$ we will use parameters $c$ and $s$.

\begin{definition} A language $L$ is in ${\BPP}_{c,s}$ 
($0\leq s(n) < c(n) \leq 1$, $\forall n \in \Nats$) if 
there exists a probabilistic polynomial time Turing Machine $M$ such
that:
\begin{enumerate}
\item $\forall w \in L, Pr[\mbox{$M$ accepts $w$}] \geq c(|w|)$
\item $\forall w \notin L, Pr[\mbox{$M$ accepts $w$}] \leq s(|w|)$
\end{enumerate}
\end{definition}

The function $c(n)$, where $n$ is the length of the input to $M$, is 
called the {\em{completeness}} and the function $s(n)$ is called the 
{\em{soundness}} of the probabilistic polynomial time Turing machine.
It turns out that the exact values of $c$ and $s$ don't matter because
of the following theorem:

\begin{theorem}[Amplification of \BPP] For all choices of 
polynomially computable functions $c(n)$ and  $s(n)$, $\{0,1\}^n \mapsto
[0,1]$, such that there exists a polynomial $Q(n)$ such that $\forall n$
$c(n) - s(n) \geq \frac{1}{Q(n)}$, and $m = O(1)$, 
\[{\BPP}_{c,s} = 
{\BPP}_{1-\frac{1}{2^{n^m}},
\frac{1}{2^{n^m}}} \ .\]
\end{theorem}

\begin{proof}
We will show that, given a \BPP \   machine $M$ with completeness $c(n)$ and 
soundness $s(n)$, we can construct a \BPP \   machine for the same language, with
completeness $1 - \frac{1}{2^{n^m}}$, soundness $\frac{1}{2^{n^m}}$, for any 
$m = O(1)$.

Consider a machine $M'$ that does the following: 

\begin{enumerate}
\item Run $M$ on $k$ independently chosen random tapes $R_1, ..., R_k$.
\item Accept if the number of times $M$ accepted  is greater than or
equal to $k(\frac{c(n)+s(n)}{2})$.
\end{enumerate}

Let $X_i$ be the indicator random variable for the event that $M$ 
accepts $w$ on random string $R_i$. By the definition of $\BPP_{c,s}$, we
know that 
$w \in L \Rightarrow \mbox{E}[X_i] \geq c(n)$, 
$w \notin L \Rightarrow \mbox{E}[X_i] \leq s(n)$. 
Let us estimate the completeness and soundness values of $M'$:
\[c_{M'}(n) = 1 - \mbox{Pr}\mbox{\Huge{[}}\sum_{i=1}^{k} X_i < k\mbox{\Huge{(}}\frac{c(n) + s(n)}{2}\mbox{\Huge{)}} \  | \  w \in L\mbox{\Huge{]}}\]
\[s_{M'}(n) = \mbox{Pr}\mbox{\Huge{[}}\sum_{i=1}^{k} X_i > k\mbox{\Huge{(}}\frac{c(n) + s(n)}{2}\mbox{\Huge{)}} \  | \  w \in L\mbox{\Huge{]}}\]

Here Chernoff bounds give us a powerful tool. Chernoff bounds guarantee that
for any $k$ independent identically distributed
 random variables $X_1, ..., X_k$, taking on values in 
the interval $[0,1]$, with expected value $\mbox{E}[X_i] = p$, for any value of
$\epsilon \in [0,1]$,
\[
\mbox{Pr}\mbox{\Huge{[}}\sum_{i=1}^{k} X_i < kp(1 - \epsilon)
\mbox{\Huge{]}} 
\leq e^{-\frac{\epsilon^2}{3}pk}
\]
\[
\mbox{Pr}
\mbox{\Huge{[}}
\sum_{i=1}^{k} X_i > kp(1 + \epsilon)
\mbox{\Huge{]}}  
\leq e^{-\frac{\epsilon^2}{3}pk}
\]
Using Chernoff bounds, setting $\epsilon$ so that $\epsilon \leq \frac{c(n) - s(n)}{2c(n)}$
and $\epsilon \leq \frac{c(n) - s(n)}{2s(n)}$
(so that $\frac{c(n)-s(n)}{2} \leq  c(n)(1-\epsilon)$ and
$\frac{c(n)-s(n)}{2} \geq  s(n)(1+\epsilon)$),
and setting $k$ such that $k \geq \frac{3n^m}{c(n)\epsilon^2}$ and
$k \geq \frac{3n^m}{s(n)\epsilon^2}$ (so that $\frac{\epsilon^2}{3}c(n)k 
\geq n^m$ and $\frac{\epsilon^2}{3}s(n)k \geq n^m$),
we get
that
\[  
c_{M'}(n) = 1 - \mbox{Pr}
\mbox{\Huge{[}}
\sum_{i=1}^{k} X_i < k
\mbox{\Huge{(}}
\frac{c(n) + s(n)}{2}
\mbox{\Huge{)}}
 \  | \  w \in L
\mbox{\Huge{]}}  
 \geq 
1-e^{-\frac{\epsilon^2}{3}c(n)k} \geq 1 - 2^{-n^m} \]
\[ 
s_{M'}(n) = \mbox{Pr}
\mbox{\Huge{[}}
\sum_{i=1}^{k} X_i > k
\mbox{\Huge{(}}
\frac{c(n) + s(n)}{2}
\mbox{\Huge{)}}
 \  | \  w \notin L
\mbox{\Huge{]}}  
 \leq 
e^{-\frac{\epsilon^2}{3}s(n)k} \leq 2^{-n^m}
\]
Since $c(n)$ and $s(n)$ differ at least by the inverse
of polynomial $Q(n)$, $k$ is polynomial in $n$. Therefore $M'$ is a probabilistic
polynomial time Turing machine with the desired properties. 
\end{proof}


\section{\BPP \   is in \Ppoly}
\begin{theorem} $\BPP \subseteq \Ppoly$.
\end{theorem}

\begin{proof}
Consider an arbitrary language $L \in \BPP$.
By definition of \BPP, we know that for any fixed string $w$ of length $n$, 
there is a random string $R$ of 
length polynomial in $n$ such that a \BPP \  machine gives the right answer if
it is given $R$ on its random tape. The idea is to find a string $R$ 
that is good for all input strings of size $n$.
By aplification of \BPP, we know that there exists a Turing machine
$M \in \BPP_{1-\frac{1}{2^{n^2}},\frac{1}{2^{n^2}}}$ that decides $L$. 
Note that the probability of making an error is much smaller than the
number of possible inputs. 

Classify all possible random strings $R$ as follows:
\begin{itemize}
\item $R$ is {\em bad} for a specific input $w$ if $M(x,R)$ gives the wrong 
answer;
\item $R$ is {\em bad} if there exists an input string $w$ for which 
$R$ is {\em bad}.
\item $R$ is {\em good} otherwise.
\end{itemize}

For a fixed input $w$, Pr[$R$ is {\em bad} for $w$] $\leq \frac{1}{2^{n^2}}$.
Then, overall, 
\[\mbox{Pr[$R$ is {\em bad}]} \leq \sum_{w \in \{0,1\}^n}^{ \ }\mbox{Pr[$r$ is
{\em bad} for $w$]} \leq 2^n \frac{1}{2^{n^2}} < 1 \ . \]
Therefore, 
\[\mbox{Pr[$R$ is {\em good}]}= 1 - \mbox{Pr[$R$ is {\em bad}]} > 0 \ . \] 
Therefore, there exists
a polynomial size advice string for any input of length $n$.
\end{proof}

\section{\BPP \   is in $\Sigma_2^P$}
It will also be useful to look at how \BPP \ fits into the polynomial 
hierarchy.
\begin{figure}
\hspace*{\fill}{\epsfxsize = 5in \epsfbox{Anna-containments.eps}}\hspace*{\fill}
\caption{The containments of some complexity classes}
\end{figure} 
Figure 1 illustrates what is known about the relationship between \polytime, 
\RP, \coRP, \BPP, \NP \ and \coNP. It also illustrates the following theorem:

\begin{theorem}$\BPP \subseteq \Sigma_2^P$
\end{theorem}

\begin{proof}
Suppose $L \in \BPP$. We wish to show that there is a $\Sigma_2^P$ machine 
that decides $L$. More specifically, we will show that there is a deterministic
polynomial time Turing machine $M(x,y,z)$ such that  
\[ x \in L \Leftrightarrow \exists y \mbox{ such that }\forall z \ M(x,y,z) = 1\]
\[ x \notin L \Leftrightarrow \forall y \exists z \mbox{ such that } 
M(x,y,z) = 0 \]  
This proof is originally due to Michael Sipser, later it was 
impoved by Clemens Lautemann. 

Say $A$ is a \BPP machine that uses $Q(n)$ random bits with 
completeness $c(n) = \frac{1}{2}$ and soundness $s(n) = 
\frac{1}{3Q(n)}$,
where $n$ denotes the length of the input string and $Q(n)$ is a 
polynomial. 
$A$ can also be viewed as
a deterministic machine that takes a random tape as an input and behaves
deterministically ever after. Consider the space $R$ of all random strings 
that can be on $A$'s random tape on input of size $n$. 
There are $2^{Q(n)}$ strings in $R$. 

Define the shift operation $F_s(y)$ 
of $y \in R$ by $s \in R$ as $F_s(y) = y \oplus s$. A shift operation is
random if its operator $s$ is chosen uniformly at random. 

Imagine a new machine, $A'(x, y, S)$, where $S$ is a sequence of random 
shift operators $(s_1, \ldots, s_k)$, $y \in R$, and $x$ is the original
input whose membership in $L_A$ is being tested. $A'$ is a deterministic
machine such that:
\[A'(x,y,S) = 1 \Leftrightarrow 
\exists s_i \in S, A \mbox{ accepts } x \mbox{ with }y\oplus s_i 
\mbox{ on its random tape.}\]

If $x \notin L_A$, and a specific $S$ is chosen at random, then 
\setcounter{equation}{0}
\begin{eqnarray}
\Pr_{y \in R}
[A'(x,y,S) = 1] & = &
\Pr_{y \in R}
[\exists s_i \in S \mbox{ such that } A(x,y\oplus s_i)] \\
& \leq &
\sum_{i = 1}^{k}
\Pr_{y \in R}
[A(x, y\oplus s_i)] \\
& \leq &
k\Pr_{y \in R}
[A(x,y)] \\
& \leq & \frac{k}{3Q(n)}
\end{eqnarray}
(1) follows from the way $A'$ was defined. (2) is a fact from
probability. (3) follows because $y\oplus s_i$ is distributed 
uniformly over $R$, just as $y$. (4) follows from the way we 
defined $A$.

Picking $k \leq 2Q(n)$ will make sure that 
\[\Pr_{y \in R}[A'(x,y,S) = 1] \leq \frac{2}{3} \ ,\] 
and that means that
\[\Pr_{y \in R}[A'(x,y,S) = 0] > \frac{1}{3} \ ,\] 
which implies that, if $x \notin L_A$,
then for any $S \in R^k$ there exists a $y \in R$ such that $A'(x,y,S) = 0$. 

If $x \in L_A$, and a specific $y$ is chosen at random, consider the 
probability that $A'$ will reject $x$ when given $y$ and some random
$S$:
\setcounter{equation}{0}
\begin{eqnarray}
\Pr_{S \in R^k}[A'(x,y,S) = 0] &=&
\Pr_{S \in R^k}[\forall s_i \in S, A(x, y\oplus s_i)=0]\\
&=& \Pr_{S \in R^k}[\forall s_i \in S, A(x,s_i) =0]\\
&\leq& (\frac{1}{2})^k
\end{eqnarray}
(1) follows from the way $A'$ was defined. (2) is true because $s_i$ is
distribited identically to $s_i \oplus y$. (3) follows from the fact that
the $c(n) \geq \frac{1}{2}$.

Finally, consider the probability that there exists a $y \in R$ such that
$A'(x,y,S)$ will reject:
\setcounter{equation}{0}
\begin{eqnarray}
\Pr_{S \in R^k}[\exists y \mbox{ such that } A'(x,y,S) = 0] 
&\leq& \sum_{y \in \{0,1\}^Q(n)}^{ \ }\Pr_{S \in R^k}[A'(x,y,S) = 0] \\
&=&2^{Q(n)}\Pr_{S \in R^k}[A'(x,y,S) = 0] \\
&\leq&\frac{2^{Q(n)}}{2^k} \ . 
\end{eqnarray}

Let $k = 2Q(n)$. Then 
\setcounter{equation}{0}
\begin{eqnarray}
\Pr_{S \in R^k}[\forall y\in R, \ A'(x,y,S) = 1]
&=& 1 - \Pr_{S \in R^k}[\exists y \mbox{ such that } A'(x,y,S) = 0] \\
&\geq&1 - \frac{2^{Q(n)}}{2^{2Q(n)}} \\
&=& 1 - \frac{1}{2^{Q(n)}} \\
&>& 0 \ .
\end{eqnarray}
This implies that if $x \in L_A$, then there exists a sequence of shifts
$S \in R^k$, such that for all $y \in R$, $A'(x,y,S)$ accepts.

To summarize, we know that 
\[ x \in L_A \Rightarrow \exists S \in R^k \mbox{ such that }
\forall y \in R, \ A'(x,y,S) = 1 \ , \]
\[ x \notin L_A \Rightarrow \forall S \in R^k \ \exists y \in R \mbox{ such that }
A'(x,y,S) = 0 \ . \] 

Therefore,
\[ x \in L_A \Leftrightarrow \exists S \in R^k \mbox{ such that }
\forall y \in R, \ A'(x,y,S) = 1 \ , \]
and so a $\Sigma_{2}^{P}$ machine can decide $L_A$ by 
guessing $S$, guessing all $y$ and checking that $A'(x,y,S) = 1$.
\end{proof}

We can use some steps of this proof to learn more facts about \BPP. 
For example, consider the following:
\begin{proposition}
$\BPP \subseteq \RP^{\coRP}$.
\end{proposition}
\begin{note}
This notation is not precise, because no \coRP-complete language is known. 
What it means is that, if given an oracle for the right \coRP \  language, 
an oracle \RP \  machine can decide any \BPP \ language.
\end{note}

\begin{proof-idea}
Imagine a machine that accepts if it can find a string $S \in R^k$
such that its oracle says that $\forall y \in R, \ A'(x,y,S) = 1$. Then
this oracle machine is an \RP \ machine, by the definition of \RP. Now,
the claim says that the oracle it uses decides a language in \coRP. 
That is so, because this oracle accepts if it cannot find a $y \in R$
such that $A'(x,y,S) \neq 1$, which, by definition of \coRP, defines
a \coRP \ language.
\end{proof-idea}

\end{document}