\documentstyle{article}
\input{preamble.tex}
\newcommand{\floor}[1]{\lfloor#1\rfloor}
\newcommand{\Floor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\ceiling}[1]{\lceil#1\rceil}
\newcommand{\Ceiling}[1]{\left\lceil#1\right\rceil}
\newcommand{\class}[1]{\mathsf{#1}}
\newcommand{\GapP}{\class{Gap\!-\!P}}


\begin{document}
\lecture{10}{March 11, 1997}{Daniel A. Spielman}{Daniel Lewin}

\section*{Toda's Theorem}

\begin{theorem}
$PH \subseteq P^{\#P}$
\end{theorem}


We will present a proof of Toda's theorem (simpler than the original)
that makes use of two new objects: a class of functions called $\GapP$
and a class of circuits called $AC_0$. In this lecture we will define
these objects and prove the properties needed for the proof of Toda's
theorem.

\section{$\GapP$}

Let $M$ be a non-deterministic Turing Machine. We denote by $\#M(x)$
the number of accepting computation paths of $M$ on input $x$, and by
$\#\overline{M}(x)$ the number of rejecting computation paths.

\begin{definition}
If $M$ is a non-deterministic Turing Machine, we define the function 
$gap_M : \sum^* \rightarrow Z$ as:
\begin{eqnarray*}
 gap_M(x) = \#M(x) - \#\overline{M}(x)
\end{eqnarray*}
\end{definition}

$gap_M$ represents the gap between the number of accepting computation
paths and the number of rejecting computation paths of $M$.

\begin{definition}
\begin{eqnarray*}
\GapP = \{gap_M \ |\ \mbox{M is a non-determenistic polynomial time Turing
Machine}\}
\end{eqnarray*}

In other words, $\GapP$ is the set of functions that are $gap_M$ for some
non-deterministic polynomial time Turing Machine.
\end{definition}

Intuitively, the difference between the classes $\#P$ and $\GapP$ is
that unlike $\#P$, $\GapP$ is closed under {\em subtraction}. In
addition, $\GapP$ has many other natural closure and composition
properties that $\#P$ does not posess.

The reason that we are interested in $\GapP$ in the context of Toda's 
theorem is the following observation which is easy to prove~\cite{Gap}.

\begin{observation}
$P^{\GapP} = P^{\#P}$
\end{observation}

\begin{proposition} 
If $f,g \in \GapP$ then:
\begin{enumerate}
\item $-f \in \GapP$

\item $f+g \in \GapP$

\item $f \cdot g \in \GapP$

\item $\sum_{\abs{y} \leq p(\abs{x})} f(x,y) \in \GapP$ 

\item $\prod_{y \leq p(\abs{x})} f(x,y) \in \GapP$ (note that $y$
is taken to be an integer in binary representation)
\end{enumerate}
\end{proposition}

\begin{proof}

Let $M_f$ and $M_g$ be the non-det poly-time TM's such that $f =
gap_{M_f}$ and $g = gap_{M_g}$.

\begin{enumerate}

\item Just swap accepting and rejecting states in $M_f$.

\item The machine $M_{g+f}$ makes a non-deterministic decision at the first 
step to simulate $M_f$ or to simulate $M_g$ on the given input.
$gap_{M_{f+g}} = \#M_f + \#M_g - \#\overline{M}_f - \#\overline{M}_g =
gap_{M_f} + gap_{M_g} = f + g$.

\item The machine $M_{g \cdot f}$ works as follows:
\begin{itemize}
\item Simulate $M_f$
\item If $M_f$ accepts, simulate $M_g$ and accept iff $M_g$ accepts.
\item If $M_f$ rejects, simulate $M_g$ and accept iff $M_g$ rejects.
\end{itemize}
We have: $gap_{M_{f \cdot g}} = \#M_{f \cdot g} - \#\overline{M}_{f \cdot g} 
= (\#M_f \cdot \#M_g + \#\overline{M}_f \cdot \#\overline{M}_g) - (\#M_f \cdot
\#\overline{M}_g + \#M_g \cdot \#\overline{M}_f) = (\#M_f - \#\overline{M}_f) \cdot
(\#M_g - \#\overline{M}_g) = gap_{M_f} \cdot gap_{M_g} = f \cdot g$.

Note that each time we carry out this multiplication operation the
running time of the resulting machine doubles. Thus, this construction
can only be carried out a polynomial number of times.

\item Non-deterministically choose $y$ and then simulate $M_f$ on $(x,y)$.

\item Iterate the multiply operation. Note that since $y$ is taken to be
the binary representation of an integer and we require $y <
p(\abs{x})$, we only multiply a polynomial number of times.

\end{enumerate}
\end{proof}

\section{$AC_0$}

\begin{definition}
$AC_0$ is the class of predicates computable by (languages accepted by)
uniform, {\em constant} depth,  polynomial sized circuits with NOT gates 
and {\em unbounded} fan-in AND and OR gates.
\end{definition}

 \begin{definition} ~\cite{Dan} A {\em probabilistic polynomial} is a
polynomial in two types of variables: actual variables $x_1, \ldots ,
x_n$ from, $\{0,1\}$, and probabilistic variables $r_1, \ldots, r_l$
where each $r_i$ is chosen uniformly and independently from $\{0,1\}$.
If $P$ is a probabilistic polynomial, then for any given $x_1, \ldots,
x_n$ we think of $P(x_1, \ldots, x_n)$ as a random variable. Let $P$
be a probabilistic polynomial and let $f$ be a function in $n$
variables. $P$ {\em computes $f$ with error $\epsilon$} if for every
$x_1, \ldots, x_n$, the probability that $P(x_1, \ldots, x_n) = f(x_1,
\ldots, x_n)$ is at least $1-\epsilon$.
\end{definition}
We will show that every $f(x_1, \ldots, x_n)$ in $AC_0$ can be
computed with small error by a low degree probabilistic polynomial
with small sample space (with a poly-logarithmic number of probabilistic
variables).

\begin{lemma}
For every family $\{A_n\}$ in $AC_0$ there exists a family of
probabilistic polynomials $\{p_n\}$ over $Z$ such that: $p_n$ has
degree $\log(n)^{O(1)}$, has $\log(n)^{O(1)}$ probabilistic
variables, and computes $A_n$ with error at most $1/3$. In other words:

\begin{eqnarray*}
\forall x : \Pr{A_n(x) = P_n(x,\vec{r})} \geq \frac{2}{3}
\end{eqnarray*}
Where the probability is over $\vec{r} \in \{0,1\}^{\log(n)^{O(1)}}$.

\end{lemma}

We make use of the results from ~\cite{ValVaz}. In particular the
following theorem (which was saw in class):

\begin{theorem} ~\cite{ValVaz} \label{VVtheorem}
Let $S \subseteq \{0,1\}^k$ be non-empty. Suppose $r_0,r_1,\ldots,r_k$ 
are randomly chosen from $\{0,1\}^k$. Let $S_0 = S$ and let $S_i$ be:
\begin{eqnarray*}
\{v \in S : v \cdot r_0 \equiv v \cdot r_1 \equiv \ldots 
  v \cdot r_{i} \equiv 0\ (mod\ 2)\}
\end{eqnarray*}
for each $i \in \{0, \ldots, k\}$. Then 
\begin{eqnarray*}
\Pr{|S_i| = 1\ \mbox{for some} \ i \in \{0, \ldots, k\}} \geq \frac{1}{4}
\end{eqnarray*}
\end{theorem}

We begin by showing that such a family of polynomials exists for
unbounded fan-in NOR gates.  

\begin{lemma}
Let $\{A_n\}$ be the family of unbounded fan-in NOR gates ($A_n$ has
$n$ inputs). There exists a family of probabilistic polynomials
$\{p_n\}$ over $Z$ such that: $p_n$ has degree $\log(n)^{O(1)}$, has
$\log(n)^{O(1)}$ probabilistic variables, and computes $A_n$ with
error at most $1/3$.
\end{lemma}
\begin{proof}
Let $x_1, \ldots, x_n$ be the inputs to $A_n$, and let $k =
\lceil\log(n)\rceil$.  Consider elements of $\{0,1\}^k$ as indexes to
the inputs. For $\vec{j} \in \{0,1\}^k$ and a vector of $k$
probabilistic variables $\vec{r}$ let $VV(\vec{j},\vec{r})$ be the
polynomial computing the function which is $1$ if $\vec{j} \cdot
\vec{r} = 0\ (mod\ 2)$ and $0$ otherwise. (This polynomial is the
arithmatization of the boolean expression $r_{t_1} \oplus r_{t_2}
\oplus \ldots \oplus r_{t_g} \oplus 1$ where the $t$'s are the
non-zero bit indices of $\vec{j}$) Let $S=\{\vec{j} \in \{0,1\}^k :
x_{\vec{j}} = 1\}$, and let the $S_i$'s be defined as in
Theorem~\ref{VVtheorem} where the bits of each $\vec{r_i}$ are taken from
different sets of probabilistic inputs. The important point is that
$|S_i|$ can be computed by the following probabilistic polynomial:

\begin{eqnarray*}
S_i(x_1, x_2, \ldots, x_n, \vec{r_1}, \vec{r_2}, \ldots, \vec{r_k}) =
\sum_{\vec{j} \in \{0,1\}^k} x_{\vec{j}} \left(\prod_{l=1}^i
VV(\vec{j},\vec{r_l}) \right)
\end{eqnarray*}
 
Where the $\vec{r}$'s are sets of $k = \log(n)$ probabilistic variables.
Note that the number of probabilistic variables is $k^2$. Consider
the polynomial
\begin{eqnarray*}
T(x_1, x_2, \ldots, x_n, \vec{r_1}, \vec{r_2}, \ldots, \vec{r_k}) =
\prod_{i=1}^k \left(1-S_i(x_1, x_2, \ldots, x_n, \vec{r_1}, \vec{r_2},
\ldots, \vec{r_k})\right)
\end{eqnarray*}

$T$ has real variables $x_1, \ldots, x_n$ and $k^2$ probabilistic variables.

Now, if all the $x_i$'s are zero then $|S_i| = 0$ for all $i$, so $T =
1$.  On the other hand, if at least one $x_i$ is 1, then by
Theorem~\ref{VVtheorem}, we have that some $|S_i| = 1$, and thus $T=0$
with probability at least $1/4$. We can reduce the error probability
from $3/4$ to $1/3$ by constructing a {\em constant} number of
polynomials that use different probabilistic variables and multiplying
them together. Thus, the total number of probabilistic variables is
$\log(n)^{O(1)}$, and the degree of the polynomial also turns out to be
$\log(n)^{O(1)}$.

\end{proof}



\begin{thebibliography}{9}

\bibitem{Gap} Stephen A. Fenner, Lance J. Fortnow, Stuart A. Kurtz,
Gap-Definable Counting Classes, http://www.cs.uchicago.edu/$\sim$fortnow/gaps.ps.Z

\bibitem{Dan} Richard Beigel, Nick Reingold, Daniel Spielman,
The Perceptron Strikes Back, http://www-math.mit.edu/~spielman

\bibitem{ValVaz} L.G. Valiant V.V Vazirani, NP is as Easy as Detecting Unique
Solutions, Theoretical Computer Science 47 (1986) 85-93

\end{thebibliography}

\end{document}