\documentclass{article}
\usepackage{amsmath,amsthm}
\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{\PsP}{\text{P}^{\text{\#P}}}

\newtheorem*{todatheorem}{Toda's Theorem}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{lpart}{Part}[lemma]

\begin{document}

\header{6.841/18.405J Advanced Complexity Theory}{March 12, 2003}
{10: Toda's Theorem}
{Prof. Madhu Sudan}{Max Goldman}

\section{$\PsP$}

\subsection{Definition and Properties}

$\text{\#P}$ is the class of functions expressible as the number of
accepting paths of a nondeterministic Turing machine. So
$$f_M(x)=|\{y\ |\ M(x,y)\text{ accepts}\}|,\ M\text{ poly-time two-input
TM}\Rightarrow f_M(x)\in\text{\#P}$$
Thus $\text{P}^{\text{\#P}}$ is the class of languages decidable in polynomial
time with oracle access to some $\text{\#P}$ function. We can note that
\begin{align*}
\text{NP}\subseteq\ &\PsP\\
\text{coNP}\subseteq\ &\PsP\\
\text{BPP}\subseteq\ &\PsP\\
\text{PP}\subseteq\ &\PsP\text{, where PP requires only a strict majority to be
correct, as opposed to }\tfrac{2}{3}\text{ for BPP}\\
&\PsP\subseteq\text{PSPACE, but }\PsP\overset{?}{=}\text{PSPACE is an open
question}
\end{align*}
Complete functions for $\text{\#P}$ include:
\begin{itemize}
\item \#SAT: $\phi\rightarrow$ number of satisfying assignments of $\phi$
\item \#HAMCYCLE: $G\rightarrow$ number of Hamiltonian cycles in $G$
\item In fact, \#CYCLE is \#P-complete by reduction from \#HAMCYCLE
\item Computing the permanent of a matrix, roughly equivalent to the number of
perfect matchings in a bipartite graph; it is worth noting that the permanent
computation is very similar to that of the determinant, and the transformation
can be done in the case of planar matrices, but this result shows that if it
could be done in general, many of our strong beliefs would be violated
\end{itemize}
Finally, we note that similar to $\text{BPP}\subseteq\Sigma_2^{\text{P}}$, we
can show that
$\text{approx-\#P}\subseteq\Sigma_3^{\text{P}}\cap\Pi_3^{\text{P}}$.

\section{$\text{PH}\subseteq\PsP$}

\subsection{Operators on Complexity Classes}
An operator $\mathcal{O}$ transforms one complexity class into a new one,
where $\mathcal{O}\in\{\text{BP},\exists,\forall,\text{co},\oplus\}$. We
define these operators for a language $L=\{x,y\}$ as
\begin{align*}
\oplus(L)&=\{x\ |\text{ number of }y\text{'s for which
}(x,y)\in L\text{ is odd}\},\ \exists,\ \forall\text{ similar}\\
\text{BP}(L)&=\left\{\begin{aligned}
x\in\Pi_{\text{YES}}&\Rightarrow\underset{y}{\text{Pr}}[(x,y)\in
L]\geq1-2^{-|x|}\\
x\in\Pi_{\text{NO}}&\Rightarrow\underset{y}{\text{Pr}}[(x,y)\in L]\leq2^{-|x|}
\end{aligned}\right.
\end{align*}
On a class $\mathcal{C}$, we have
$\mathcal{O}\cdot\mathcal{C}=\{\mathcal{O}(L)\ |\ L\in\mathcal{C}\}$. Defining
the BP operator in this strong manner (exponentially small error as opposed to
a constant fraction) will simply the results to follow.

\subsection{Toda's Theorem: \small Part 1 of $n$}
\begin{todatheorem}
$\text{PH}\subseteq\PsP$
\end{todatheorem}

We prove this theorem by means of two essentially separate lemmas, from which
the desired result follows directly.

\begin{lemma}
\label{lemmaone}
$\text{PH}\subseteq\text{BP}\cdot\oplus\cdot\text{P}$
\end{lemma}

\begin{lemma}
\label{lemmatwo}
$\text{BP}\cdot\oplus\cdot\text{P}\subseteq\PsP$
\end{lemma}

In order to prove these two lemmas, we first note the following:

\setcounter{claim}{-1}%
\begin{claim}
\label{opsclosecomp}
Operators BP and $\oplus$ preserve closure under complementation
\end{claim}

\noindent\emph{Argument for Claim \ref{opsclosecomp}.}
The statement is that
$\text{co}\cdot\text{BP}\cdot\mathcal{C}\subseteq\text{BP}\cdot\mathcal{C}$,
for $\mathcal{C}$ closed under complementation.

In the case of BP, $\text{BP}(L)\in\text{BP}\cdot\mathcal{C}$, and
$\text{BP}(\overline{L})=\overline{\text{BP}(L)}$.

For $\oplus$, we see that, for example, if $(\phi,a)\in L$,
$$\oplus(L)=\{\phi\ |\ \phi\text{ has an odd number of satisfying
assignments}\}$$
We can find the complement with the mapping
$\phi(x_1,...,x_n)\rightarrow\phi'(x_0,x_1,...,x_n)$, where $\phi'$
is satisfied if either $x_0=1\text{ and }x_1=...=x_n=0$ or $x_0=0\text{ and
}\phi(x_1,...,x_n)=1$, which adds one to the number of satisfying
assignments.

\setcounter{lemma}{\ref{lemmaone}}%

\noindent\emph{Proof of Lemma \ref{lemmaone}.}
This proof is done in two parts:

\begin{lpart}
\label{onesubone}
$\exists\cdot\mathcal{C}\subseteq\text{BP}\cdot\oplus\cdot\mathcal{C}$, where
$\mathcal{C}=\text{BP}\cdot\oplus\cdot\text{P}$
\end{lpart}

\begin{lpart}
\label{onesubtwo}
$\text{BP}\cdot\oplus\cdot\text{BP}\cdot\oplus\cdot\text{P}\subseteq\text{BP}\cdot\text{BP}\cdot\oplus\cdot\oplus\cdot\text{P}\subseteq\text{BP}\cdot\oplus\cdot\text{P}$
\end{lpart}

Part \ref{onesubone} also implies that
$\forall\cdot\mathcal{C}\subseteq\text{BP}\cdot\oplus\cdot\mathcal{C}$, so any
level of the polynomial hierarchy can be expressed as
$\text{BP}\cdot\oplus\cdot\text{BP}\cdot\oplus\cdots\text{BP}\cdot\oplus\cdot\text{P}$.
Applying Part \ref{onesubtwo} a finite number of times at each level yields
$\text{PH}\subseteq\text{BP}\cdot\oplus\cdot\text{P}$ to prove Lemma
\ref{lemmaone}.

\begin{proof}[Proof of Part \ref{onesubone}]
We begin by showing $\text{NP}\subseteq\text{BP}\cdot\oplus\cdot\text{P}$, by
amplifying the $\tfrac{1}{\text{poly}}$ result used previously to show USAT is
NP-hard under randomized reductions. Recall the Valiant-Vazirani reduction:
$$\phi\overset{?}{\in}\text{SAT}\rightarrow\psi\overset{?}{\in}\text{USAT}:\left\{
\begin{aligned}
\phi\in\text{SAT}&\rightarrow\psi\text{ has one satisfying assignment w.p.
}\tfrac{1}{n}\\
\phi\not\in\text{SAT}&\rightarrow\psi\text{ has zero satisfying assignments}
\end{aligned}\right.$$
Applying this random reduction many times yields several formulas $\psi_i$:
\begin{eqnarray*}
\phi\in\text{SAT}&\rightarrow&
\left.\begin{matrix}
\psi_1\\\vdots\\\psi_m
\end{matrix}\right\}\ 
\begin{matrix}\text{at least one has an odd number
of}\\\text{\ \ \ satisfying assignments w.h.p.}\end{matrix}\\
\phi\not\in\text{SAT}&\rightarrow&\left.\begin{matrix}
\psi_1\\\vdots\\\psi_m
\end{matrix}\right\}\text{ all have an even number}
\end{eqnarray*}
We then need to combine $\psi_1\ldots\psi_m$ into a single formula
$\widehat{\psi}$ such that if all $\psi_i$ are even, $\widehat{\psi}$ is even,
and if some $\psi_i$ are odd, $\widehat{\psi}$ is odd w.h.p. Applying a parity
flip makes this easier; we now need to find a $\widehat{\psi}$ that is odd if
all $\psi_i$ are odd and is even otherwise. If we have each $\psi_i(x_i)$
operating on the set of variables $x_i$, then we simply use
$$\widehat{\psi}(x_1\ldots x_m)=\bigwedge_{i=1}^m\psi_i(x_i)$$
This gives $\text{NP}\subseteq\text{BP}\cdot\oplus\cdot\text{P}$. The same
method works to show
$\exists\cdot\text{BP}\cdot\oplus\cdot\text{P}\subseteq\text{BP}\cdot\oplus\text{BP}\cdot\oplus\cdot\text{P}$,
which proves Part \ref{onesubone} of the lemma.
\end{proof}

\subsection{Operators and Circuits}

It can be useful to think of complexity class operators in terms of
constructing a circuit, where each operator is a gate with fan-in equal to the
number of assignments it quantifies over. Operators $\forall$, $\exists$, and
co correspond to the usual AND, OR, and NOT gates, respectively, and $\oplus$
is of course a parity gate. BP corresponds to an ``approximate majority''
gate, which passes on the majority of its inputs with some error. The result
of Part \ref{onesubone} above shows that any OR gate in the circuit can be
replaced by an approximate majority gate followed by parity gates. We use this
understanding of operators to begin the proof of Part \ref{onesubtwo} in the
next section.

\subsection{Toda's Theorem: \small Part 2 of $n$}

\noindent\emph{Proof of Part \ref{onesubtwo}.}
Recall the claim of \ref{onesubtwo}, that
$\text{BP}\cdot\oplus\cdot\text{BP}\cdot\oplus\cdot\text{P}\subseteq\text{BP}\cdot\text{BP}\cdot\oplus\cdot\oplus\cdot\text{P}\subseteq\text{BP}\cdot\oplus\cdot\text{P}$.
This requires that the innermost operators be flipped, and then adjacent
operators eliminated. In circuit terms, the flip consists of taking a parity
gate whose inputs are BP ``approximate majority'' gates, and switching them to
yield a single BP gate fed by several parity gates. This is done without
making any changes to the surrounding circuit.

If the original circuit has a parity gate quantifying over variable $y$ with
fan-in $2^a$ and BP gates over $z$ each with fan-in $2^b$, the new circuit
will have a BP gate and $2^b$ parity gates each with fan-in $2^a$. These
arrangements are shown in Figures \ref{fig-circ-orig} and \ref{fig-circ-new}.
We let $2^{-c}$ be the error of the original BP gate.

\setlength{\unitlength}{1cm}
\newcommand{\somewires}{\put(.8,.62){\line(-2,-5){.2}}
                        \put(.9,.59){\line(-1,-5){.1}}
                        \put(1,.58){\line(0,-1){.5}}
                        \put(1.1,.59){\line(1,-5){.1}}
                        \put(1.2,.62){\line(2,-5){.2}}}
\newcommand{\circuitdia}[6]{
\begin{picture}(7,4)
\multiput(1,1)(1,0){4}{\circle{.8}}
\multiput(.6,.6)(1,0){4}{\makebox(.8,.8){#2}}
\put(4.6,.6){\makebox(.8,.8){$\cdots$}}
\put(6,1){\circle{.8}}
\put(5.6,.6){\makebox(.8,.8){#2}}
\qbezier(2,2)(3.5,1.5)(5,2) \put(5.1,1.9){#3}
\put(3.5,2.5){\circle{.8}}
\put(3.1,2.1){\makebox(.8,.8){#1}}
\put(4,1){\qbezier(-.4,-.6)(0,-.7)(.4,-.6)} \put(4.5,.3){#4}
\put(6,1){\qbezier(-.4,-.6)(0,-.7)(.4,-.6)} \put(6.5,.3){#4}
\put(.2,.3){#6}
\put(1.8,2.2){#5}
\put(3.5,2.92){\line(1,6){.1}}
\multiput(0,0)(1,0){4}{\somewires}
\put(5,0){\somewires}
\put(3.5,2.5){\put(-.35,-.25){\line(-2,-1){1.86}}
              \put(-.2,-.38){\line(-4,-3){1.04}}
              \put(-.1,-.41){\line(-1,-3){.23}}
              \put(.1,-.41){\line(1,-3){.23}}
              \put(.35,-.25){\line(2,-1){1.86}}}
\end{picture}
}
\begin{figure}[b]
\begin{minipage}[t]{.45\textwidth}\begin{center}
\circuitdia{$\bigoplus$}{\textsf{BP}}{$2^a$}{$2^b$}{$y$}{$z$}
\caption{Original circuit}
\label{fig-circ-orig}
\end{center}\end{minipage}
\hfill
\begin{minipage}[t]{.45\textwidth}\begin{center}
\circuitdia{\textsf{BP}}{$\bigoplus$}{$2^b$}{$2^a$}{$z$}{$y$}
\caption{Circuit after transformation}
\label{fig-circ-new}
\end{center}\end{minipage}
\end{figure}

Picking a random $z$, we see that the $z^{\text{th}}$ parity gate in the new
circuit computes the incorrect value if there exists a $y$ such that the
original BP gate for that $y$ is incorrect. By simply counting the error of
each original BP gate, we see that
$$\begin{aligned}\text{Pr}[z^{\text{th}}\ \oplus\text{ in new circuit
incorrect}]&\leq\text{Pr}[\exists y\text{ s.t. BP in original circuit
incorrect}]\\
&\leq2^b\cdot2^{-c}
\end{aligned}$$
Thus, by ensuring that $c$ is larger than $b$, we can push the error rate
arbitrarily low. This shows that the quantifier switch is correct; the rest
remains to be shown... in another lecture.

\end{document}