\documentclass[10pt]{article}
\usepackage{amsfonts}
\newcommand{\p}{\mathop{\rm P}}
\newcommand{\bpp}{\mathop{\rm BPP}}
\newcommand{\np}{\mathop{\rm NP}}
\newcommand{\conp}{\mathop{\rm co-NP}}
\newcommand{\atisp}{\mathop{\rm ATISP}}
\newcommand{\obj}{\mathop{\rm Obj}}
\newcommand{\prob}[2]{Pr_{#1}[#2]}
\newcommand{\ppoly}{{\p/_{\rm poly}}}

%\usepackage{epsfig}

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

\lecture{11}{Mar 14, 2007}{Madhu Sudan}{Tim Abbott}

%%%% body goes in here %%%%

\section{Overview}

This lecture describes $\bpp$ amplification, shows $\bpp \subset
\ppoly$, and shows that $\bpp$ is contained within the polynomial
hierarchy.  Finally, we have an introductory discussion of randomized
rounding for unique SAT.

\section{BPP Amplification}

\begin{definition}
  A language $L$ is in \emph{$\textrm{Strong BPP}$} if for any polynomial $q(n)$, there exists a
  polynomial time machine $M(\cdot, \cdot)$ such that for any $x \in
  \{0, 1\}^n$, we have that either $x \in L$ and
  \[
  Pr_y\left[M(x, y) \textrm{accepts}\right] \ge 1 - 2^{- q(n)}
  \]
  or $x \not \in L$ and
  \[
  Pr_y\left[M(x, y) \textrm{accepts}\right] \le 2^{- q(n)}
  \]
  
\end{definition}
\begin{remark}
In this discussion, we will consider a machine polynomial time if its
time is polynomial in the length of the first argument.  The part of
the second argument (the random bits) that the machine can ever
examine will consequently be polynomial in the length of the first
argument, so we can assume that it is polynomial in the size of the
first argument.
\end{remark}


\begin{definition}
  A language $L$ is in \emph{$\textrm{Weak BPP}$} if there exists a
  polynomial time machine $M(\cdot, \cdot)$, a polynomial $p(n)$, and
  a polynomial time computeable function $s(n)$, such that for any $x
  \in \{0, 1\}^n$, we have that either $x \in L$ and
  \[
  Pr_y\left[M(x, y) \textrm{accepts}\right] \ge s(n) + \frac{1}{p(n)}
  \]
  or $x \not \in L$ and
  \[
  Pr_y\left[M(x, y) \textrm{accepts}\right] \le s(n)
  \]
\end{definition}

\begin{theorem}[Amplification Theorem]
  Strong BPP = Weak BPP
  \end{theorem}

\begin{proof}
Clearly, Strong BPP is contained in Weak BPP, so we must show that
Weak BPP is contained in Strong BPP.  Suppose $L$ is in Weak BPP, and
fix a polynomial $q(n)$.  We have a polynomial $p(n)$, machine $M$,
and polynomial time computeable function $s(n)$ satisfying the weak
BPP property.  We will define an algorithm $M'$ as follows.  Pick
$y_1, \ldots, y_t$ independently and identically from the distribution
of possible random inputs for $M$, and for each $y_i$, compute $z_i =
M(x, y_i)$.  Let $\overline{z} = \frac{\sum_{i=1}^n z_i}{t}$.  Then
$M'$ accepts if and only if $\overline{z} \ge s(n) + \frac{1}{2
p(n)}$.  We will seperate out the two cases $x \in L$ and $x \not \in
L$.

We will need to use the Chernoff Bound:

\begin{theorem}[Chernoff Bound = Tail Inequality = Hoeffding Bound]
  Suppose $z_1, \ldots, z_t$ are bounded (say in $[0, 1]$), and are
  independently and identically distributed, with mean $\mu$.  Then
\[
Pr \left[ \left|\overline{z} - \mu \right| \ge \epsilon \right] \le
e^{-\Omega(\epsilon^2 t)}
\]
\end{theorem}

\begin{remark}
There are cases in which one can strengthen this bound, but we won't
be needing the stronger versions.  
  \end{remark}


Suppose now that $x \in L$.  The $y_i$'s are independent and
identically distributed with $\mu \ge s(n) + \frac{1}{p(n)}$.  By the
Chernoff Bound, with $\epsilon = \frac{1}{2p(n)}$ and $\mu \ge s(n) +
\frac{1}{p(n)}$, we have that
\[
Pr \left[\textrm{M' accepts } x \in L\right] = Pr \left[ \overline{z} \ge \frac{1}{2p(n)} + s(n) \right] \le Pr \left[ \left|\overline{z} - \mu \right| \ge \frac{1}{2p(n)} \right] \le
e^{-\Omega(t / p(n)^2)}
\]
For $t = \Omega(p(n)^2 q(n))$, we see that for $x \in L$, the Strong
BPP condition holds.

The argument is similar for $x \not \in L$, so the Strong BPP
conditions holds for $x \not \in L$ as well.  Thus Weak BPP equals
Strong BPP, as desired.

\end{proof}

\begin{remark}
Note the quadratic dependence on $p(n)$.  This procedure of converting
a Weak BPP algorithm to a Strong BPP algorithm costs a lot of
randomness, and time, though of course they both remain polynomial in
the input size.  
\end{remark}

\section{$\bpp \subset \ppoly$}

\begin{corollary}[Adleman]
$\bpp \subset \ppoly$
\end{corollary}
\begin{proof}
It suffices to show that Strong $\bpp$ is contained in $\ppoly$.  Let
$L \in \bpp$.  Pick as our polynomial $q(n) = 2n$.  Then $M$ accepts
$L$ with error probability $2^{-2n}$.  Suppose $M(x, y)$ is a machine
with input $x$ and random bits $y$.  We say that $y$ is \emph{wrong
  advice} for $x$ if $M(x, y) \not = L(x)$.  Then
\[
Pr_y \left[\textrm{$y$ is wrong for $x$} \right] \le 2^{-2n}
\]
Using the fact that there are at most $2^n$ values of $x$ of length
$n$, we have by the Union Bound that
\[
Pr_y \left[\textrm{There exists an $x$ such that $y$ is wrong for $x$}
  \right] \le 2^n * 2^{-2n} = 2^{-n}
\]
Since this probability is less than 1, there exists some $y$ such that
$y$ is wrong for no $x$, i.e. there exists a $y$ such that $M(x, y) =
L(x)$ for all $x$ of length $n$.  Using this $y$ as the advice, we
have that $L \in \ppoly$, as desired.  

\end{proof}

\begin{remark}
Since $\bpp \subset \ppoly$, if we had that $\np \subset \bpp$, we
would then have that $\np \subset \ppoly$.  But $\np \subset \ppoly$
implies that the polynomial hierarchy collapses, which we think is
quite unlikely.  Thus, this corollary suggests that $np \not \subset
\bpp$, or that nondeterministic polynomial time is more powerful than
randomized polynomial time.
\end{remark}

\section{$\bpp \subset \Sigma_2^P$}

\begin{theorem}[Sipser, Lautemann]
$\bpp$ is contained in the polynomial hierarchy.  In particular, $\bpp
\subset \sum_2^P$
\end{theorem}
\begin{proof}
In $\Sigma_2^P$, we have a short interaction between the prosecution,
who is trying to show that $x \in L$, and the defense, who is trying
to show that $x \not \in L$.  First, the prosecution sends a message
to the defense, and then the defense sends a reply.  The jury, who
sees both messages, must then decide in polynomial time whether or not
$x$ is in $L$.  

Suppose $L \in \bpp$.  Then we have $M$, which uses $l$ random bits,
and has error probability $2^{-q(n)}$ for some polynomial $q(n)$.
Suppose $x$ is an input for $L$.  Let us iterate through a few ideas
for how to do this proof.

\begin{enumerate}
\item[Idea 1.] The prosecution sends $y \in \{0, 1\}^l$, and the jury
accepts if $M(x, y)$ does.  But since $\bpp$ has false positives, the
prosecution could do this for $x \not \in L$, and this idea doesn't work.
\item[Idea 2.] The defense sends  $y \in \{0, 1\}^l$, and the jury
rejects if $M(x, y)$ does.  But since $\bpp$ has false negatives, the
prosecution could do this for $x \in L$, and this idea doesn't work.
\item[Idea 3.] The defense sends most of the bits of $y$, and the
  prosecution picks the rest.  Since if $x \in L$, most values of $y$
  cause $M$ to accept, the prosecution should be able to succeed,
  while if $x \not \in L$, most values of $y$ cause $M$ to reject, so
  the defense should be able to pick his bits of $y$ such that no
  choice on the prosecution's part causes $M$ to accept.  This is on
  the right track, but requires the defense to pick first, and isn't
  yet a protocol.  
\item[Idea 4.] The prosecution picks a list $y_1, \ldots, y_k$, and
  then the defense picks some $y$.  The jury then considers $y \oplus
  y_i$, for each $y_i$, and if $M(y \oplus y_i)$ accepts for any $i$,
  then the jury accepts, otherwise it rejects.
\end{enumerate}

We will use the algorithm of Idea 4.  First, suppose $x \in L$.
We say that $y_i$ is \emph{wrong} for $y$ if $M(x, y\oplus y_i)$
rejects.  Then using the Strong BPP property, for any $y$, 
\[
Pr_{y_i} \left[\textrm{$y_i$ is wrong for $y$} \right] \le 2^{-q(n)} \le \frac12.
\]
If the $y_i$'s are picked independently at random, then
\[
Pr_{y_1, \ldots, y_k} \left[\textrm{$y_i$ is wrong for $y$ for all $i$} \right] \le 2^{-k}
\]
Thus, by the union bound, we have that
\[
Pr_{y_1, \ldots, y_k} \left[\textrm{There exists $y$ such that for all
    $i$, $y_i$ is wrong for $y$} \right] \le 2^{l-k}
\]
Thus if we pick $k > l$, then for any $y$, there must exist some set
of $y_i$'s that are not all wrong for $y$.  The prosecution can then
pick these $y_i$'s, and regardless of what $y$ the defense picks, the
jury will decide that $x \in L$, as desired.

Suppose, then, that $x \not \in L$.  Here we say that $y$ is wrong for
$y_i$ if $M(x, y \oplus y_i$ accepts.  Fix $q(n) = n$, so that $k$ and
$l$ are both polynomial in $n$.  Then we have that

\[
Pr_{y} \left[\textrm{$y$ is wrong for $y_i$} \right] \le 2^{-q(n)} \le 2^{-n}
\]
Then by the union bound, 
\[
Pr_{y} \left[\textrm{There exists $i$ such that $y$ is wrong for
    $y_i$} \right] \le k 2^{-n} = poly(n) 2^{-n} < 1
\]
Thus, there must exist some choice of $y$ for which no $i$ exists
where $y$ is wrong for $y_i$.  Thus the defense can pick this $y$, and
the jury will find that $M(x, y \oplus y_i)$ rejects for each $i$, and
thus will reject $x$, as desired.  We have thus shown that $\bpp
\subset \Sigma_2^P$.  
\end{proof}

\section{Randomized Reductions}
Randomization can help prove results in complexity theory that on
their face, have nothing to do with randomness.  Such reductions are
called randomized reductions.  Our first example will be in
constructing one-way permutations.  We know that if $\p = \np$, modern
cryptography doesn't work.  But what if $\p \not = \np$?  We don't
know how to show that this implies modern cryptography is strong.  

\begin{definition}
$f: \{0,1\}^n \rightarrow \{0,1\}^n$ is a \emph{one-way permutation}
  if $f$ is a bijection and $f(x)$ is easy to compute from $x$, yet
  $x$ is hard to compute from $f(x)$.  
\end{definition}

For cryptography, we'd like to know that for a random $x$, the one-way
permutation is hard to invert.  Here, we will only show that there
exist $x$ for which the one-way permutation is hrad to invert.  

Consider the following idea for constructing a one-way permutation,
given that $\p \not = \np$.  Given $(\phi, x)$ such that $\phi(x) =
1$, where $\phi$ is a CNF formula, we send it to $\phi$.  It is easy
to compute $\phi$ from $(\phi, x)$.  But the opposite, computing
$(\phi, x)$, given only $\phi$, requires solving satisfiability.
Unfortunately, this mapping is not one-to-one, so it is not a one-way
permutation (it is instead a one-way function).  So, if we had a
$\phi$ that was an element of Unique-SAT, the problem of finding a
satisfying assignment when we know that there is a unique solution,
and Unique-SAT was NP-hard, then we could use such a $\phi$, and we'd
be done.  So, we must study the Unique-SAT problem: Given a formula
$\phi$ that has a unique satisfying assignment, does there exist an
efficient algorithm to find it?  

\begin{theorem}[Valiant, Vazirani]
  Unique-SAT is hard.
\end{theorem}
In this lecture, we will just sketch the proof, which will be given
formally next time.  
We will use a randomized reduction to convert an instance of SAT into
an instance of a promise problem related to Unique-SAT. It will send:
\begin{itemize}
\item SAT $\rightarrow$ Unique-SAT
\item $\phi \rightarrow \psi$, probabilistically.
\item $\phi \in SAT \rightarrow \psi$ that has a unique satisfying
  assignment, with probability $\frac{1}{p(n)}$.
\item $\phi \not \in SAT \rightarrow \psi$ with not satisfying
  assignment, with probability 1.
\end{itemize}

Since $\phi$ is satisfiable, it has for some $1 \le m \le n$, between
$2^{m-1}$ and $2^m$ satisfying assignments.  We will guess $m$
(costing at most polynomial probability of success, since there are
only $n$ distinct possibly values of $m$), and do the following.  Let
$h: \{0,1\}^n \rightarrow \{0, 1\}^m$.  We will define $\psi(x) = 1$
if and only if both $\phi(x) = 1$ and $h(x) = 0^m$.  We hope that with
probability bounded below by $\frac{1}{p(n)}$, this will give us a
formula $\psi$ that has a unique satisfying assignment, but is still
hard.  Thus, we need $h$ to be both efficiently computeable, and
``random''.  These cannot be simulataneously true, so we'll have to do
some sort of compromise.  In the next lecture, we will formalize this
notion. 

\end{document}