\documentclass[A4, 11 pt]{llncs}
%\usepackage{amsmath, amssymb, amsthm, fullpage}
\usepackage{amssymb, amsmath, fullpage}

%\input{/Users/ananthr/tex-macros/macros.tex}
%\usepackage[charter]{mathdesign}
\usepackage{times}
\renewcommand{\ttdefault}{cmtt}

\long\def\symbolfootnote[#1]#2{\begingroup%
\def\thefootnote{\fnsymbol{footnote}}\footnote[#1]{#2}\endgroup}
\newcommand{\cfootnote}[2]{\symbolfootnote[#1]{#2}}

% -- tabbed environment for algorithm descriptions --
\newenvironment{RawAlg}{\begin{tabbing}%
000 \= 000 \= 000 \= 000 \= 000 \= 000 \= 000 \= 000 \= 000 \= 000 \= \kill}%
{\end{tabbing}}
\newenvironment{alg}
{\begin{quote}\begin{RawAlg}}
{\end{RawAlg} \end{quote}}

% -- math symbols -- 
\renewcommand{\qed}{\hspace{1pt}\rule[-1pt]{4pt}{9pt}}
\newcommand{\Z}{\ensuremath{\mathbb{Z}}}
\newcommand{\F}{\ensuremath{\mathbb{F}}}
\newcommand{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\ring}{\ensuremath{\mathbf{R}}}
\newcommand{\C}{\ensuremath{\mathbb{C}}}
\newcommand{\Q}{\ensuremath{\mathbb{Q}}}
\newcommand{\G}{\ensuremath{\mathbb{G}}}
\newcommand{\zo}{\ensuremath{\{0,1\}}}
\renewcommand{\iff}{\ensuremath{\Leftrightarrow}}
\newcommand{\Iff}{\ensuremath{\Longleftrightarrow}}
\newcommand{\xor}{\ensuremath{\oplus}}
\newcommand{\Xor}{\ensuremath{\bigoplus}}
\newcommand{\andl}{\ensuremath{\wedge}}
\newcommand{\orl}{\ensuremath{\vee}}
\newcommand{\union}{\ensuremath{\cup}}
\newcommand{\intersect}{\ensuremath{\cap}}
\newcommand{\Union}{\ensuremath{\bigcup}}
\newcommand{\Intersect}{\ensuremath{\bigcap}}
\renewcommand{\implies}{\ensuremath{\Rightarrow}}
\newcommand{\Implies}{\ensuremath{\Longrightarrow}}
\newcommand{\deq}{\ensuremath{:=}}
\renewcommand{\phi}{\ensuremath{\varphi}}
\newcommand{\dfrom}{\ensuremath{\stackrel{R}{\leftarrow}}}
\newcommand{\eps}{\ensuremath{\varepsilon}}
\newcommand{\set}[1]{\ensuremath{\left[#1\right]}}
\newcommand{\opt}{\ensuremath{\textsc{Opt}}}
\newcommand{\innerp}[2]{\ensuremath{\left\langle#1,#2\right\rangle}}
\newcommand{\norm}[1]{\ensuremath{\left\|#1 \right\|}}

% -- text in math mode -- 
\newcommand{\ppoly}[0]{{\rm poly}}
\newcommand{\poly}[1]{\ensuremath{{\rm poly}\left(#1\right)}}
\newcommand{\polylog}[1]{\ensuremath{{\rm polylog}\left(#1\right)}}
\renewcommand{\Pr}{\ensuremath{{\rm Pr}}}
\renewcommand{\th}{\ensuremath{^{\rm th}}}
\newcommand{\mystar}[1]{\ensuremath{#1^*}}
\newcommand{\myexp}{\ensuremath{\mathbb{E}}} %expectation

% -- complexity classes -- 
\newcommand{\NP}{\ensuremath{\mathbf{NP}}}
\newcommand{\coNP}{\ensuremath{\mathbf{co{\sf -}NP}}}
\newcommand{\BPP}{\ensuremath{\mathbf{BPP}}}
\newcommand{\RP}{\ensuremath{\mathbf{RP}}}
\newcommand{\PSPACE}{\ensuremath{\mathbf{PSPACE}}}
\newcommand{\PH}{\ensuremath{\mathbf{PH}}}
\newcommand{\sharpP}{\ensuremath{\mathbf{\# P}}}
\newcommand{\E}{\ensuremath{\mathbf{E}}}
\renewcommand{\P}{\ensuremath{\mathbf{P}}}
\newcommand{\EXP}{\ensuremath{\mathbf{EXP}}}
\newcommand{\SAT}{\ensuremath{{\sf SAT}}}
\newcommand{\TQBF}{\ensuremath{{\sf TQBF}}}
\newcommand{\psp}{\ensuremath{\P/\ppoly}}
\newcommand{\logvc}{\textsc{Log-VC}~}
\newcommand{\logis}{\textsc{Log-IS}~}

% -- crypto related stuff -- 
\newcommand{\Exper}{\ensuremath{\mathsf{Exp}}}
\newcommand{\Funs}{\ensuremath{\mathsf{Funs}}}
\newcommand{\Adv}{\ensuremath{\mathsf{Adv}}}
\newcommand{\PRFAdv}{\ensuremath{\mathsf{PRFAdv}}}
\newcommand{\TrapGen}{\ensuremath{\mathsf{TrapGen}}}
\newcommand{\kSIS}{$k$-SIS\ } %k-SIS macro
% -- defining script adversaries
\newcommand{\A}{\ensuremath{\mathcal{A}}}
\newcommand{\B}{\ensuremath{\mathcal{B}}}

\begin{document}

\noindent {\bf CS254: Computational Complexity Theory} \\
{\bf Prof. Luca Trevisan}\\

\noindent {\bf Final Project} \\
\noindent Ananth Raghunathan\cfootnote{1}{{\tt
ananthr@cs.stanford.edu, ananthr1987@gmail.com}}

\begin{center}
\LARGE
{Toda's Theorem: $\PH \subseteq \P^\sharpP$}
\end{center}

\section{Introduction}
The class $\NP$ captures the difficulty of finding certificates. However, in
many contexts, one is interested not just in a single certificate, but
actually counting the number of certificates. In this manuscript we look at
a famous result involving $\sharpP$, (pronounced ``sharp p''), a complexity
class that captures this notion.  Counting problems arise in diverse fields,
often in situations having to do with estimations of probability. Examples
include statistical estimation, statistical physics, network design, and
more.  Counting problems are also studied in a field of mathematics called
enumerative combinatorics, which tries to obtain closed-form mathematical
expressions for counting problems.  To give an example, in the 19th century
Kirchoff showed how to count the number of spanning trees in a graph using
a simple determinant computation.

\begin{definition}
A function $f:\zo^* \to \mathbb{N}$ is in $\sharpP$ if there exists a
polynomial $p:\mathbb{N} \to \mathbb{N}$ and a polynomial time algorithm
$M$ such that for every $x \in \zo^*$:
\[
f(x)=\left| \left\{ y \in \zo^{p(|x|)}:M(x,y)=1\right\}\right|
\]
\end{definition}

The biggest open problem regarding $\sharpP$ is whether or not all problems
in this class are efficiently solvable. In other words, whether
$\sharpP=\mathbf{F}\P$ where $\mathbf{F}\P$ is the analogue class to the
class $\P$ for functions with more than 1 bit of output. Clearly, finding
the number of certificates is at least as hard as finding whether or not
there exists a certificate, therefore, if $\sharpP=\mathbf{F}\P$, certainly
$\P=\NP$. We also know that $\sharpP \subseteq \PSPACE$, because we can
count the number of certificates given polynomial amount of space.

In 1979, when Valiant introduced the class $\sharpP$, he also showed that
finding the permanent of a matrix (even when its entries are restricted to
$\zo$) is $\sharpP$-complete. But surprisingly, we also know that we can
approximately count given access to an $\NP$ oracle. In other words,
${\rm approx-}\sharpP \subseteq \BPP^{\NP}$. Since $\BPP \subseteq
\Sigma_2^{(p)}$, ${\rm approx-}\sharpP \subseteq \Sigma_3^{(p)}$.
\newline

This was the state of affairs in the 1980s, where people were interested in
the relative powers of $\PH$ and $\sharpP$. Both were considered natural
generalizations of $\NP$, although it is not immediately clear how each of
their definitions, viz.~alternation, and the ability to count certificates
were comparable in any sense. However, in 1989, Seinosuke Toda
\cite{Toda91} showed that $\sharpP$ is a very powerful language. Indeed,
with only a single call to a $\sharpP$ oracle, one can decide membership of
a quantified boolean formula in $\PH$. This came as a very surprising
result to the community and was one of the landmark results of complexity
theory. Toda's theorem therefore implies that any problem in the polynomial
hierarchy is deterministic polynomial time {\it Turing reducible} to a
counting problem. This won Toda the G\"odel prize in 1998. Here is the
citation for the G\"odel prize.

\begin{quote}
\small
In the remarkable paper ``PP is as hard as the polynomial-time hierarchy''
Seinosuke Toda showed that two fundamental and much studied computational
concepts had a deep and unexpected relationship. The first is that of
alternation of quantifiers---if one alternates existential and universal
quantifiers for polynomial time recognizable functions one obtains the
polynomial time hierarchy. The second concept is that of counting the exact
number of solutions to a problem where a candidate solution is polynomial
time recognizable. Toda's astonishing result is that the latter notion
subsumes the former---for any problem in the polynomial hierarchy there is
a deterministic polynomial time reduction to counting. This discovery is
one of the most striking and tantalizing results in complexity theory. It
continues to serve as an inspiration to those seeking to understand more
fully the relationships among the fundamental concepts in computer science.
\end{quote}

\begin{theorem}[Toda \cite{Toda91}] $\PH \subseteq \P^{\sharpP}$
\end{theorem}

\subsection{Preliminaries} \label{prelim}

We use $\xor$ to denote a parity quantifier that is formally defined below:
\begin{definition}
The quantifier $\xor$ is defined as follows: For every Boolean formula
$\phi$ on $n$ variables, $\Xor_{(x \in \zo^n)} \phi(x)$ is true iff the
number of $x$'s such that $\phi(x)$ is true is odd. The language $\xor\SAT$
denotes the set of all true quantified Boolean formulae of the form
$\Xor_{(x \in \zo^n)} \phi(x)$ where $\phi$ is an unquantified Boolean
formula (not necessarily in CNF).
\end{definition}
\begin{note}
If we identify true with 1 and false with 0,
$\Xor_{(x\in\zo^n)}\phi(x)=\sum_{x\in\zo^n}\phi(x)\;({\rm mod}\;2)$. Also,
$\Xor_{(x\in\zo^n)}\phi(x)=\Xor_{(x_1\in\zo)}\Xor_{(x_2\in\zo)}\cdots\Xor_{(x_n\in\zo)}\phi(x_1,\ldots,x_n)$
\end{note} \vspace{0.1in}

Let $\phi$ be a boolean formula. We denote by $\#(\phi)$ the number of
solutions to $\phi$.  Given two unquantified formulae $\phi(x)$ and
$\phi(y)$, define:
\begin{itemize}
\item $\phi\cdot\phi'$ as the formula $\phi(y) \land \phi'(z)$ where $y$
and $z$ are two disjoint sets of variables. It is easy to see that
$\#(\phi\cdot\phi')=\#(\phi)\cdot \#(\phi')$.
\item $\phi+\phi'$ as the formula $(w \land \phi(y)) \lor (\overline{w}
\land \phi'(y))$, where $w$ is a single additional boolean variable. Then,
$\#(\phi+\phi')=\#(\phi)+\#(\phi')$.
\item 1 is an arbitrary formula with exactly one satisfying assignment.
\end{itemize} 

Therefore, it follows immediately that:
\begin{align*}
\left(\Xor_x\phi(x)\right) \land \left(\Xor_y\psi(y)\right) &\iff \Xor_{x,y}
(\phi\cdot\psi)(x,y)\\
\neg \left(\Xor_x\phi(x)\right) &\iff \Xor_{x,z}
(\phi+1)(x,z)\\
\left(\Xor_x\phi(x)\right) \lor \left(\Xor_y\psi(y)\right) &\iff
\Xor_{x,y,z} ((\phi+1)\cdot(\psi+1)+1)(x,y,z)\\
\end{align*}

\section{Valiant-Vazirani Theorem}
One of the key constructions that will be used (repeatedly) in the proof of
Toda's theorem is the randomized reduction of Valiant-Vazirani of \SAT to
Unique-\SAT. We will use a weaker corollary of the Valiant-Vazirani theorem
as stated below:

\begin{theorem}[Valiant-Vazirani \cite{VV86}]
There exists a probabilistic polynomial time algorithm $A$ such that for
every $n$-variable Boolean formula $\phi$, we have:
\begin{align*}
\phi \in \SAT &\implies \Pr\left[A(\phi) \in \text{{\rm Unique}-\SAT}\right] \geq
\frac{1}{8n} \\
\phi \not\in \SAT &\implies \Pr\left[A(\phi) \text{ {\rm is satisfiable}}\right]
= 0.
\end{align*}
\end{theorem}

In particular, since $A(\phi)$ has a unique solution, it is a member of
$\xor\SAT$. Also, if $A(\phi)$ has no solutions, then it does not belong to
$\xor\SAT$. Thus, the Valiant-Vazirani theorem implies the following Lemma.

\begin{lemma} \label{vv}
There exists a probabilistic polynomial time algorithm $A$ such that for
every $n$-variable Boolean formula $\phi$, we have:
\begin{align*}
\phi \in \SAT &\implies \Pr\left[A(\phi) \in \xor\SAT\right] \geq
\frac{1}{8n} \\
\phi \not\in \SAT &\implies \Pr\left[A(\phi) \in \xor\SAT\right]
= 0.
\end{align*}
\end{lemma}

One interpretation of the Valiant-Vazirani theorem is that given an
algorithm to distinguish whether or not a formula had exactly one or zero
satisfying assignments, then we can construct a randomized algorithm that
would decide NP-complete problems, which would imply that $\NP=\RP$.

Extending upon this interpretation, if we could somehow determine if a
formula had an even number or an odd number of satisfying assignments, then
we can construct a randomized algorithm that would solve everything in the
polynomial hierarchy.

Although this does not prove Toda's theorem (because the result is
deterministic) it does show that $\PH \subseteq \BPP^{\xor\P}$. We require
oracle access to a $\sharpP$ oracle to derandomize this reduction.

\section{Toda's Theorem}
As discussed in the previous section, we begin by constructing a randomized
algorithm to decide problems in $\PH$ given oracle access to a $\xor\P$
oracle. We start off with the following lemma:
\begin{lemma} \label{first}
Let $c \in \mathbb{N}$ be a constant and $\TQBF$ be the set of all true
quantified boolean formulas. There exists a probabilistic
polynomial time algorithm $B$ such that for every $\phi$, a quantified
boolean formula with $c$ levels of alternations,
\begin{align*}
\phi \in \TQBF &\implies \Pr\left[B(\phi) \in \xor\SAT\right] \geq
\frac{2}{3} \\
\phi \not\in \TQBF &\implies \Pr\left[B(\phi) \in \xor\SAT\right] =0.
\end{align*}
\end{lemma}

To derandomize, we need another lemma:
\begin{lemma} \label{second}
There is a deterministic polynomial time transformation $T$, that, for
every input formula $\phi$ that is an input for $\xor\SAT$, constructs
$\psi=T(\phi,1^m)$, an unquantified boolean formula such that:
\begin{align*}
\phi \in \xor\SAT &\implies \#(\psi) = -1 \;({\rm mod}\; 2^{m}) \\
\phi \not\in \xor\SAT &\implies \#(\psi) = 0 \;({\rm mod}\; 2^{m}).
\end{align*}
\end{lemma}

\begin{proof}[Toda's theorem]
Equipped with the above two lemmas, we prove Toda's theorem. In the next
section, we show the proofs of the two lemmas. We are given an input
quantified boolean formula $\phi$ with $c$ alternations, for some constant
$c$ and we need to determine whether or not $\phi \in \TQBF$.

First consider the reduction $B$ from Lemma \ref{first}. Since $B$ is
randomized, we can consider it as a deterministic procedure that takes in a
random string $r$ of length $m-1$ along with the input $\phi$ and outputs a
formula $\psi_r$ depending on the input $r$. Applying $T(\cdot,1^m)$ from
Lemma \ref{second} to $\psi_r$, we obtain a formula $\psi_r'$.
\newline

Now, consider the following quantity:
$K=\mathop{\sum}_{r \in \zo^{m-1}} \#(\psi_r')$,
which counts the number of {\it pairs} $(x,r)$ such that assignment $x$
satisfies the formula $\psi_r'$. We look at the following two cases:
\begin{itemize}
\item Case 1: If $\phi \not\in \TQBF$, then regardless of
the choice of $r$, $\#(\psi_r') = 0\;({\rm mod}\; 2^m)$. Therefore
$K=0\;({\rm mod}\; 2^m)$.
\item Case 2: If $\phi \in \TQBF$, then for at least $2/3$ fraction of the
strings $r$, we have $\#(\psi_r)$ is odd. Then this also implies that for
at least $2/3$ fraction of the strings $r$, $\#(\psi_r')=-1\;({\rm
mod}\;2^m)$, and for the remaining at most $1/3$ fraction,
$\#(\psi_r')=0\;({\rm mod}\;2^m)$. Thus, $K$ must fall in the range
$[-\frac23 2^{m-1},-2^{m-1}] \;({\rm mod}\;2^m)$, which necessarily means
that $K \neq 0\;({\rm mod}\;2^m)$.
\end{itemize}

Now, we have our $\P^{\sharpP}$ algorithm to decide $\phi$. We run the
reductions from Lemmas \ref{first} and \ref{second} and ask a $\sharpP$
oracle to count the number of pairs $(x,r)$ such that $x$ satisfies
$\psi_r'$.\footnote{By the Cook-Levin theorem, we can construct such a
boolean formula because the reductions all run in polynomial time.} If the
answer divides $2^m$, then we reject; otherwise accept.
\qed
\end{proof}

\section{Proof of Lemmas \ref{first} and \ref{second}}
In this section, we prove the two lemmas used in the previous section.

\begin{proof}[Lemma \ref{first}]
We can assume without loss of generality that the first quantifier is
$\xor$, because we see how a $\exists$ quantifier is converted to a
$\xor$ below. We can also use the identities $\forall_xP(x)=\neg
\exists_x\neg P(x)$ to transform the boolean expression.

Let's start with the base case, when there is only one quantifier. We are
given $\phi(x,y)$ and we need to determine if $\Xor_x \exists y: \phi(x,y)$
is true nor not. Let $|x|=|y|=n$. For the moment, forget about $x$ and focus
on $y$. What can we do? We use Valiant-Vazirani (Lemma \ref{vv}) to
randomly produce a formula $\phi'(x,y)$ such that if $\phi(x,y)$ is
satisfiable, then $\phi'(x,y)$ is uniquely satisfiable with a probability
at least $1/8n$, and unsatisfiable otherwise.
\newline

Suppose, the Valiant-Vazirani reduction were deterministic then the formula
$\Xor_y:\phi'(x,y)$ would be equivalent to $\exists y:\phi(x,y)$ and
therefore the $\xor\SAT$ instance $\Xor_x \Xor_y: \phi'(x,y)$ and $\Xor_x
\exists y: \phi(x,y)$ would also be equivalent.

Since the reduction is randomized and fails sometimes, we need to repeat
the reduction several times to obtain $\phi'(x,y)$ such that
$\Xor_y:\phi'(x,y)$ and $\exists y:\phi(x,y)$ are equivalent with
probability at least $1-\frac16 2^{-n}$. Now, we can use the union bound to
get:
\[
\Pr \left[ \text{For all $x$, } \Xor_y:\phi'(x,y) \equiv \exists y:\phi(x,y) 
\right] \geq \frac56
\]
therefore, in particular,
\[
\Pr \left[ \Xor_{x,y}:\phi'(x,y) \equiv \Xor_x \exists y:\phi(x,y) 
\right] \geq \frac56
\]
Thus, we are able to get rid of one level of quantification
(probabilistically).
\newline

But, how do we construct $\phi'$ from $\phi$. If we run the
Valiant-Vazirani reduction $t=O(n^2)$ times independently, we produce
formulae $\phi_1'(x,y),\ldots,\phi_t'(x,y)$. If $\phi(x,y)$ is satisfiable,
we know that at least one of the $t$ formulae has a unique satisfying
assignment with probability $\geq 1-\frac16 2^{-n}$, and otherwise, none of
them have a satisfying assignment.

Thus, given $\phi_1',\ldots,\phi_t'$ produce a single $\phi'$ such that
$\Xor_y:\phi'(x,y)$ is true iff at least for one $i$, $\Xor_y:\phi_i'(x,y)$
is true. For this, recall the construction in section \ref{prelim}
\[
\left(\Xor_x\phi(x)\right) \lor \left(\Xor_y\psi(y)\right) \iff
\Xor_{x,y,z} ((\phi+1)\cdot(\psi+1)+1)(x,y,z)\\
\]
Therefore, setting:
\[
\phi'(x,y) \deq
1+\left(1+\phi_1'(x,y)\right)\cdots\left(1+\phi_t'(x,y)\right)
\]
we construct $\phi'$ that has an odd number of satisfying assignments iff
at least one of the $\phi_i'$ does.
\newline

This proves the result in the case there is one alternation. To extend this
to $c$ levels of alternation, we use the same argument to eliminate the
outermost existential quantifier, and use the fact that $\psi \in
\xor\Pi_{k-1}\SAT \iff \overline{\psi} \in \xor\Sigma_{k-1}\SAT$.
Of course, this requires the probabilities to be arranged such that $c$
repetitions of this succeeds with probability at least $2/3$. To do this,
it suffices for us to succeed one step with a probability of at least
$1-1/(6c^2)$, so that the reduction succeeds with probability:
\[
1-\sum_c\left(\frac{1}{6c^2}\right) \geq \frac23.
\]
\qed
\end{proof}

\begin{proof}[Lemma \ref{second}]
For every pair of formulae $\phi$ and $\psi$ recall the definitions
$\phi+\psi$ and $\phi\cdot\psi$. Note that each of the constructions are of
a size at most a constant factor larger than $\phi$ and $\psi$. Consider
the formula $\psi^6+2\psi^3$ (where $\psi^3$, for example is $\psi \cdot
(\psi \cdot \psi)$). One can easily check that:
\begin{align*}
\#(\psi)=-1\;({\rm mod}\;2^{2^i}) &\implies \#(\psi^6+2\psi^3)=-1\;({\rm
mod}\;2^{2^{i+1}}) \\
\#(\psi)=0\;({\rm mod}\;2^{2^i}) &\implies \#(\psi^6+2\psi^3)=0\;({\rm
mod}\;2^{2^{i+1}}).
\end{align*}
Therefore, if we set $\tau_0=\phi$ and $\tau_{i+1}=\tau_i^6+2\tau_i^3$,
then after $\log{m}$ steps, we get that $\psi=\tau_{\log{m}}$ satisfies the
two conditions in Lemma \ref{second}. The size of $\psi$ is only
polynomially larger than the size of $\phi$ (because at each stage the
overhead is a constant factor).
\qed
\end{proof}

\nocite{RU07, Toda91, F09, BA09}
\bibliographystyle{splncs}
\bibliography{todathm.bib}

\end{document}
