\documentclass[10pt]{article}
\usepackage{amsfonts}
\newcommand{\p}{\mathop{\rm P}}
\newcommand{\ph}{\mathop{\rm PH}}
\newcommand{\bp}{\mathop{\rm BP}}
\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{fullpage}
\usepackage{paralist}
\usepackage{graphics}
\usepackage{wrapfig}
\usepackage{graphicx}
\usepackage{tree-dvips}
\newcommand{\lb}{\bigskip}
\newcommand{\id}{\hspace{20pt}}

%\usepackage{epsfig}
\begin{document}
\input{preamble.tex}


\newcommand{\st}{\textrm{ s.t. }}
\newtheorem{property}{Property}[theorem]

\lecture{11}{Mar 14, 2007}{Madhu Sudan}{Igor Ginzburg, Adam Lerer}

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

\section{Administrative}
\begin{itemize}
	\item PS2 is graded and available from Swastik.
	\item PS3 is out and due Friday 4/6.
\end{itemize}

\section{Overview}
In this lecture we prove the two containments of Toda's Theorem:
\begin{enumerate}
	\item $\ph \subseteq \bp \cdot \oplus \cdot \p$
	\item $\bp \cdot \oplus \cdot \p \subseteq \p^{\#\p} $
\end{enumerate}

\section{Operator Definitions}
The alternation operators acting on a language $L$ or complexity class $C$ are defined as follows:
  \[ \begin{array}{llll} 
  			{\exists \cdot L = \{x | \exists y \st (x,y) \in L\}} & {\exists \cdot C = \{\exists \cdot L | L \in C\}}
				\\
				{\forall \cdot L = \{x | \forall y \st (x,y) \in L\}} & {\forall \cdot C = \{\forall \cdot L | L \in C\}}
  			\\
  			\oplus \cdot L = \{x | \# y \st (x,y) \in L \rm{\ is\ even}\}
  			&
  			\oplus \cdot C = \{\oplus \cdot L | L \in C\}
  			\\
  			\bp \cdot L = (\Pi_{YES}, \Pi_{NO})
  			
  			&
  			\bp\cdot C = \{\bp \cdot L | L \in C\}
  		\end{array}
  \]
   \[ \Pi_{YES} = \{x | \prob{y}{(x,y) \in L} \geq 1 - \frac{1}{2^{q(n)}}\} \]
  \[ \Pi_{NO} = \{x | \prob{y}{(x,y) \in L} \leq \frac{1}{2^{q(n)}}\} \]
The classes in $\ph$ can be defined using these operators: $\Sigma_k^{\p} \exists \cdot \forall \cdot \exists \cdot ... \cdot \p$ and $\Pi_k^{\p} = \forall \cdot \exists \cdot \forall \cdot ... \cdot \p$.

\section{Toda's Theorem 1: $\ph \subseteq \bp \cdot \oplus \cdot \p$}


\begin{lemma}
$\bp \cdot \oplus \p = \bp \cdot \oplus \cdot \bp \cdot \oplus \cdot \p$
\end{lemma}

First we note that for a complexity class $C$ closed under complement, $\bp \cdot C$ is closed under complement since the error bounds for $\bp$ are symmetric.  $\oplus \cdot C$ is also closed under complement since by a method from Lecture 12 we can add exactly one satisfying assignment to a formula, flipping the parity.  Therefore all the classes we're dealing with are closed under complement.  The method from Lecture 12 also allows us to exchange `odd' for `even' in the definition of $\oplus$.\\


We see that $\bp \cdot \oplus \p \subseteq \bp \cdot \oplus \cdot \bp \cdot \oplus \cdot \p$ trivially.  The opposite containment can be shown based on some general properties:


\begin{property}
\label{oplusprop}
$\oplus \cdot \oplus \cdot C = \oplus \cdot C$.
\end{property}
\begin{proof}
For $L \in C$, let $L' = \oplus \cdot L$ and $L'' = \oplus \cdot \oplus \cdot L$. Now,
\begin{eqnarray*}
x \in L'' &\iff& \# y_1 \st (x, y_1) \in L' {\textrm { is odd}} \\
&\iff& \sum_{y_1}{L'(x, y_1) = 1 (\bmod 2)} \\
&\iff& \sum_{y_1}{\sum_{y_2}{L(x, y_1, y_2) = 1 (\bmod 2)}} \\
&\iff& \sum_{(y_1, y_2)}{L(x, y_1, y_2) = 1 (\bmod 2)} \\
&\iff& \# (y_1, y_2) \st (x, y_1, y_2) \in L {\textrm { is odd}} \\
&\iff& x \in L'
\end {eqnarray*}

So, $L'' = L'$.
\end{proof}

\begin{property}
\label{bpprop}
$\bp \cdot \bp \cdot C \subseteq \bp \cdot C$
\end{property}
\begin{proof}
Again, for $L \in C$ let $L'' = \bp \cdot \bp \cdot L$ and $L' = \bp \cdot L$.  Now,
\begin{eqnarray*}
x \in L'' &\Rightarrow& \prob{y_1}{(x, y_1) \in L'} \geq 1 - 2 ^{-q_1(n)} \\
&\Rightarrow& \prob{y_1}{\prob{y_2}{(x, y_1, y_2) \in L} \geq 1 - 2 ^{-q_2(n)}} \geq 1 - 2 ^{-q_1(n)} \\
&\Rightarrow& \prob{y_1, y_2}{(x, y_1, y_2) \in L} \geq 1 - 2 ^{-q_1(n)} - 2 ^{-q_2(n)} \\
&\Rightarrow& x \in L'
\end{eqnarray*}
Since we can similarly show that $x \not \in L'' \Rightarrow x \not \in L'$, $L'' = L'$.
\end{proof}
\begin{property}
\label{bothprop}
$\oplus \cdot \bp \cdot C \subseteq \bp \oplus \cdot C$
\end{property}
\begin{proof}
\\Fix $L \in C$.  We will show that $\oplus \cdot \bp \cdot \L \subseteq \bp \cdot \oplus \cdot C$.
\\Now, $\oplus \cdot \bp \cdot L = \{x| \# y \st \{\prob{z}{(x,y,z) \in L} \geq 1 - 2 ^{-q_1(n)}\} \textrm{ is even}\}$.
\\We define $\widetilde{L} = \{x| {\prob{z}{\#  y \st (x,y,z) \in L \textrm{ is even}} \geq 1 - 2 ^{-q_2(n)}} \}$.  $\widetilde{L}$ is clearly $\in \bp \cdot \oplus \cdot C$.  We will show that for proper $q_1(n)$ and $q_2(n)$, $\oplus \cdot \bp \cdot L = \widetilde{L}$:
\\
\\Define $L' = \bp \cdot L = \{(x, y) | \prob{z}{(x, y, z) \in L} \geq 1 - 2 ^{-q(n)} \}$.

Fix $x$.  We say that $z$ is bad for $y$ if $L(x,y,z) \neq L'(x,y)$.
\\When we fix $y$, we see that:
\[\prob{z}{z \textrm{ is bad for } y} \leq 2^{-q(n)} \]
\[\prob{z}{\exists y \st z \textrm{ is bad for } y} \leq 2^{l}2^{-q(n)} (\textrm{where }l = |y|) \]
\[\prob{z}{z \textrm{ is good for all } y} \geq 1 - 2^{l}2^{-q(n)} \]
\[\prob{z}{\forall y L(x,y,z) = L'(x,y)} \geq 1 - 2^{l}2^{-q(n)} \]
\\By choosing $q(n)$ sufficiently large, we can get that for most $z$'s, $\forall y L(x,y,z) = L'(x,y)$.  So, for most $z$'s, $\oplus \cdot L(x, z) = \oplus \cdot \L'(x)$.  Now, this is equivalent to saying that $\widetilde{L} = \oplus \cdot \L'(x) = \oplus \cdot \bp \cdot \L(x)$.

\end{proof}

\begin{lemma}
$\exists \cdot C \subseteq BP \cdot \oplus \cdot C$
\label{lemma1}
\end{lemma}
\begin{proof}
Let's look at some language $L\in C$. By the same argument given by Valiant-Varizani (an RP reduction), there is a language $L'\in C$ such that
\begin{equation}
\exists y: (x,y)\in L \Leftrightarrow Pr_z[\# y:(x,y,z)\in L'\ is\ even]\geq 1/p(n)
\end{equation}
and
\begin{equation}
\forall y: (x,y)\notin L \Leftrightarrow Pr_z[\# y:(x,y,z)\in L'\ is\ even] = 0
\end{equation}
\lb

Now, the only problem is that RP only needs a probability of $1/p(n)$ when $x\in L$, but strong-BP needs a probability $1-frac{1}{2^{-q(n)}}$. But it is easy to get the stronger probability.
\lb

\begin{equation}
L'^k = \{(x,y|\forall i: (x,y_i,z_i)\in L'\}
\end{equation}

Clearly, $L'^k$ will still be in $C$. So

\begin{equation}
\exists y: (x,y)\in L \Leftrightarrow Pr_{z_1..z_k}[\# {y_1..y_k}:(\overline{x},\overline{y},z)\in L'\ is\ even]\geq 1-(1-1/p(n))^k.
\end{equation}

Therefore, 

\begin{equation}
\exists y: (x,y)\in L \Leftrightarrow Pr_z[\# y:(x,y,z)\in L'\ is\ even]\geq 1/p(n)
\end{equation}
\lb

So $L\in BP \cdot \oplus \cdot C$.

$C$ is closed under complement, so we can easily make the same argument for $\forall \cdot C$.
\end{proof}

\begin{theorem}[Toda's Theorem 1]
  $\forall k: \Sigma_{k}^{\p}$, $\Pi_{k}^{\p} \subseteq \bp \cdot \oplus \cdot P$
\end{theorem}
\begin{proof}
We will prove by induction on $k$, where the base case of $k=0$ is trivial since  $\Sigma_0^{\p} = \Pi_0^{\p} = \p$.  We assume the induction hypothesis that $\Sigma_{k-1}^{\p}$, $\Pi_{k-1}^{\p} \subseteq \bp \cdot \oplus \cdot P$.  We will now show the inductive case using a series of containments:
\[\Sigma_{k}^{\p} = \exists \cdot \Pi_{k-1}^{\p} \subseteq \exists \cdot \bp \cdot \oplus \cdot \p \subseteq \bp \cdot \oplus \cdot \bp \cdot \oplus \cdot \p \subseteq \bp \cdot \oplus \cdot \p\]

The first containment, $\Sigma_{k}^{\p} = \exists \cdot \Pi_{k-1}^{\p}$ is true by definition.  The second containment is proven in Lemma ~\ref{lemma1}.  The last containment is true by the following:

\begin{eqnarray*}
\bp \cdot \oplus \cdot \bp \cdot \oplus \cdot \p \subseteq \oplus \cdot \oplus \cdot \bp \cdot \bp \cdot \p \ \ {\rm (by\ Property ~\ref{bothprop})} \\
\subseteq \oplus \cdot \bp \cdot \bp \cdot \p \ \  {\rm (by\ Property ~\ref{oplusprop})}\\
\subseteq \oplus \cdot \bp \cdot \p \ \ {\rm (by\ Property ~\ref{bpprop})}
\end{eqnarray*}
\end{proof}


\section{Theorem 2: $BP\cdot \oplus \cdot P\in P^{\# P}$}

Toda's theorem states that we can reduce any language in $BP \cdot \oplus \cdot P$ to a language of the form 

\begin{equation}
\label{toda2}
L_\# = \{x\ |\ 0\leq \#y\ s.t.\ (x,y)\in L\leq a(mod\ b)\}
\end{equation}

for some language $L$ and integers $a$ and $b$.
\lb

$L_\# \in P^{\# P}$, because it's just counting the satisfying $y$ values modulo some constant. In fact, if we prove this reduction, we will show that any language in $BP\cdot \oplus \cdot P$ can be decided with just one query to a $\# P$ oracle.
\lb

Let $L$ be some language in $P$ and let $L' \in BP \cdot \oplus \cdot P$ be defined as:

\begin{equation}
x\in L' \Rightarrow Pr_y[\# z\{(x,y,z)\in L\} = 1 (mod\ 2)]\geq \frac{2}{3}
\end{equation}
\begin{equation}
x\notin L' \Rightarrow Pr_y[\# z\{(x,y,z)\in L\} = 0 (mod\ 2)]\leq \frac{1}{3}
\end{equation}

We are using a weak version of $BP$ because it is all we'll need for this proof.
\lb

Let's suppose that the number of $y$ values that we're enumerating over is $\leq 2^k$. 

\lb

Now, what if we were somehow able to ``pump up'' the modulus to be $2^k$? In other words, what if we could convert $L'$ into a language defined as:
\lb

\begin{equation}
x\in L' \Rightarrow Pr_y[\# z\{(x,y,z)\in L\} = 1 (mod\ 2^k)]\geq \frac{2}{3}
\end{equation}
\begin{equation}
x\notin L' \Rightarrow Pr_y[\# z\{(x,y,z)\in L\} = 0 (mod\ 2^k)]\leq \frac{1}{3}
\end{equation} 
\lb

Then, we could remove the probability notation and write the definition as
\lb
 
\begin{equation}
x\in L' \Rightarrow \leq \# (y,z) \{(x,y,z)\in L\} \geq \frac{2}{3} \cdot 2^k (mod\ 2^k)
\end{equation}
\begin{equation}
x\notin L' \Rightarrow \# (y,z) \{(x,y,z)\in L\} \leq \frac{1}{3} \cdot 2^k (mod\ 2^k)
\end{equation}
\lb

Now \it this \rm can be calculated by a language of the form described in (~\ref{toda2})!
\lb

So how are we going to boost this modulus up to $2^k$?
\lb

Given that $\# y: \{(x,y)\in L_1\}=N_1$ and $\# y: \{(x,y)\in L_2\}=N_2$ for some $x$, we can construct languages $L_+$ and $L_{\times}$:
\lb

\begin{equation}
L_+ = \{(x,by)|(b=0\ \& \ (x,y)\in L_1)\ or\ (b=1\ \& \ (x,y)\in L_2)\}
\end{equation}
\begin{equation}
\# y: \{(x,y)\in L_+\}=N_1 + N_2
\end{equation}
\lb

\begin{equation}
L_{\times} = \{(x,(y_1,y_2))|((x,y_1)\in L_1)\ and\ ((x,y_2)\in L_2)\}
\end{equation}
\begin{equation}
\# y: \{(x,y)\in L_{\times}\}=N_1 \times N_2
\end{equation}
\lb

Combining these constructions, it is clear that if $N(x) = \# y: \{(x,y)\in L\}$, then for any $f$, we can construct a language $L_f$ such that $\# y: \{(x,y)\in L_f\}=f(N(x))$. So, we just need a function $f$ such that:

\begin{equation}
x=0\ (mod\ 2^z) \Rightarrow f(x)=0 (mod\ 2^{2z})
\end{equation}
\begin{equation}
x=1\ (mod\ 2^z) \Rightarrow f(x)=1 (mod\ 2^{2z})
\end{equation}
\lb

With such an $f$, we can iteratively apply $f$ to $x$ $k$ times, which will pump $(mod 2)$ up to $(mod 2^k)$. Well, it turns out there's no function with these properties. However, if we replace $1$ with $-1$, then there is such a function, namely $f(x)=4x^3+3x^4$.

\begin{equation}
x=0\ (mod\ 2^z) \Rightarrow 4x^3+3x^4=0\ (mod\ 2^{2z})
\end{equation}
\begin{equation}
x=-1\ (mod\ 2^z) \Rightarrow 4x^3+3x^4=-1\ (mod\ 2^{2z})
\end{equation}
\lb

So now we can construct a language from $L'$ that we can use in (~\ref{toda2}) with $a=2^{k-1}$ and $b=2^k$, thus solving $L'$ in $P^{\# P}$.

\end{document}