\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage[dvips]{graphicx}
\newtheorem{define}{Definition}
%\newcommand{\Z}{{\bf Z}}
%\usepackage{psfig}
\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in
\begin{document}
\input{preamble.tex}
\lecture{14}{March 28, 2005}{Madhu Sudan}{Alissa Reyzin}
\section{Today}
\subsection{Announcements}
\begin{itemize}
\item
Have you scribed twice? Please sign up to scribe if you haven't.
\item
Pick up graded problem set 2 from Sergey
\end{itemize}
\subsection{Toda's Theorem}
\begin{itemize}
\item Recall operators $\exists$, $\forall$, $\bigoplus$, $BP$
\item Operator Calculus $PH \subseteq BP \cdotp \bigoplus \cdotp P$
\item Arithmetic $BP \cdotp \bigoplus \cdotp P \subseteq P^{\#P} $
\end{itemize}
Although Toda's Theorem is very powerful, we still do not know whether $\#$P is
different from PSPACE. We also do not know whether it is different from
LOGSPACE.
\section{Applying Operators to Complexity Classes}
Given a complexity class $C$ and an operator $O$ we can construct a new
complexity class $O \cdotp C$. For example, we have already seen that:
\begin{itemize}
\item $\exists \cdotp P = NP$
\item $\exists \cdotp co$-$NP = \Sigma_2^P$
\item $\forall \cdotp \Sigma_2^P = \Pi_3^P$
\end{itemize}
Remember that the operator $\bigoplus$ gives us an exact count on the least
significant digit and the operator $BP$ gives an approximate count on the
total. The precise definitions of the operators are as follows.
\begin{itemize}
\item A language $L \in \exists \cdotp C$ if there exists a machine $M$ such
that $L(M) \in C$ and $L = \{x | \exists y$ such that $M(x, y) = 1\}$.
Keep in mind that the running time complexity for all classes created by
operator applications must be measured as a function of the first input,
since the later inputs can be extremely large.
\item A language $L \in \bigoplus \cdotp C$ if there exists a machine $M$ such
that $L(M) \in C$ and $ L = \{x| $ the number of $y$'s such that $M(x, y) = 1$
is odd $\}$.
Consider what happens if we replace the word ``odd'' with ``even''. This
gives us the class $co \bigoplus \cdotp P$. We can easily see that this
class is the same as $\bigoplus \cdotp P$. Consider $M'(x, by) = $ accept if
$by = \bar{0}$ or if $b = 1 $ and $M(x, y)$ accepts. This has exactly one
more accept than $M(x, y)$.
\item We use the strong definition of BP when defining the operator. The
distinction is important, since we are not guaranteed to be able to amplify
when the operator is attached to a given complexity class.
A language $L \in BP \cdotp P$ if $\forall$ polynomials $q$ there exists a
machine $M$ such that $L(M) \in C$ and $\mbox{Pr}_y[M(x, y) = ``x \in L''] \geq 1 - \frac{1}{2^{q^{|x|}}}$
\end{itemize}
\section{Proof of $PH \subseteq BP \cdotp \oplus \cdotp P$}
To show that $PH \subseteq BP \cdotp \bigoplus \cdotp P$ we need the following
steps.
\begin{eqnarray}
\mbox{(we can also show this for the
$\forall$ operator) } \exists \cdotp BP \cdotp \oplus \cdotp P \subseteq BP \cdotp \oplus
\cdotp BP \cdotp \oplus \cdotp P\\
\subseteq BP \cdotp BP \cdotp \oplus \cdotp \oplus \cdotp P \\
\subseteq BP \cdotp \oplus \cdotp \oplus \cdotp P \\
\subseteq BP \cdotp \oplus \cdotp P
\end{eqnarray}
After this has been shown, we can use induction to demonstrate that any
constant length sequence of $\forall$ and $\exists$ quantifiers can be
absorbed into the class $BP \cdotp \bigoplus \cdotp P$.
\subsection{Step 4}
We need to show that $\bigoplus \cdotp \bigoplus \cdotp C \subseteq \bigoplus
\cdotp C$
Let $L(M) \in C$
Let $L_1 = \{(x, y) | $the number of $z$ such that $M((x, y), z)$
accepts is odd $\}$. Then $L_1 \in \bigoplus \cdotp C$.
Let $L_2 = \{x | $ the number of y such that $(x, y) \in L_1$ is odd $\}$
\begin{figure}[!h]
\begin{center}
\includegraphics[scale=.5]{plusplus.ps}
\end{center}
\end{figure}
We can draw the circuits using parity operators for the above languages. We see
that all we need to show is that $\sum_y \sum_z M(x, y, z) = \sum_{(y, z)} M(x,
y, z)$. But this is obvious.
The only small caveat is that we need to have associativity. That is $M((x,y)
z) = M(x, (y, z))$. We also need to have available linear time in order to
reparenthasize.
\subsection{Step 3}
We need to show that $BP \cdotp BP \cdotp P \subseteq BP \cdotp P$.
The main idea is that instead of calculating approximate majority first over
all the $y$'s and then over all the $z$'s we do it over all pairs $(y, z)$
which will at most sum the two error probabilities.
\begin{figure}[!h]
\begin{center}
\includegraphics[scale=.5]{bpbp.ps}
\end{center}
\end{figure}
That is, we draw a circuit with $BP$ gates. Assume that the error we want in our
final circuit is $2^{-q(n)}$. Then we simply pick our $BP$ gates in the
original circuit to have error $2^{-q(n) + 1}$. At worst, the probabilities of
error will be added together, which gives us the desired probability.
\subsection{Step 2}
We need to show that $\bigoplus \cdotp BP \cdotp C \subseteq BP \cdotp
\bigoplus \cdotp C$.
\begin{figure}[!h]
\begin{center}
\includegraphics[scale=.5]{plus.ps}
\end{center}
\end{figure}
Let us call the fan out of the parity gate $2^l$ and the fanout of the BP gate
$2^m$. Suppose for a moment that the BP gate made no errors. In that case,
clearly, the switch is a valid one. Every error made can give the wrong output
of the parity gate. How many errors do we have? $2^l * 2^m * 2^-q = 2^{l + m -
q}$.
Now consider the number of parity gates computing the wrong value after the
switch. This is also at most $2^{l + m - q}$. Therefore, the probability of
error is $\frac{2^{l + m - q}}{2^m} \leq 2^{l-q}$. So, if we want $q'(n)$ to be
the probability of error, we simply choose $q(n) = q'(n) + l$.
Note that this does not work in the reverse direction, since each parity gate
may have errors.
\subsection{Step 1}
We need to show that $\exists \cdotp C \subseteq BP \cdotp \bigoplus \cdotp P$
where $C = BP \cdotp \bigoplus P$. (This does not hold true for all complexity
classes, since we need to be able to use amplification.)
\begin{figure}[!h]
\begin{center}
\includegraphics[scale=.5]{vbp.ps}
\end{center}
\end{figure}
Where have we seen a similar picture before? This looks a great deal like the
Razborov-Smolensky proof. Unfortunately, picking a random subset of an
exponential number of things costs us too much time. It is possible to use
pseudo-randomness instead of true randomness, but this requires techniques that
we haven't seen. Instead, we will try to use Valiant-Vazirani (Unique SAT in
Parity SAT).
The problem with using Valiant-Vazirani is that the error is too high. On the
other hand, the error is one sided, which makes amplification easier.
Valiant-Vazirani gives us:
\begin{itemize}
\item $\phi \mbox{ satisfiable} \rightarrow \phi' \mbox{
odd}$ with probability $1/n$
\item$\phi \mbox{ unsatisfiable} \rightarrow \phi' \mbox{
even}$ with probability 1.
\end{itemize}
What we want is:
\begin{itemize}
\item$\phi \mbox{ satisfiable} \rightarrow \phi' \mbox{
odd}$ with probability $1-2^{-n}$
\item$\phi \mbox{ unsatisfiable} \rightarrow \phi' \mbox{
even}$ with probability $1-2^{-n}$.
\end{itemize}
Let's complement everywhere. That is, let's have a satisfiable $\phi$ go to an
even $\phi'$ and an unsatisfiable $\phi$ go to an odd $\phi'$. Then, we can
calculate $\phi'_1, \phi'_2, \phi'_3 ...$ which will be completely independent
variables. Since $\#$SAT = product of $\#$SAT, we know that if all of the
$\phi'_i$ are odd, the product will be odd, otherwise it will be even. This
gives us exactly the amplification we were looking for.
Since all that we used to do the amplification was complementation and
polynomial time manipulations, this shows that $\exists$ can be replaced as
stated above.
\section{Proof of $BP \cdotp \oplus \cdotp P \subseteq P^{\#P}$}
We need to show that $BP \cdotp \oplus \cdotp P \subseteq P^{\#P}$
$\bigoplus \cdotp P \subseteq \{(\phi, t, N) |$ the number of accepting
configurations$ \in \{0, 1\} (\bmod N)\}$. We accept if the number of
accepting configurations is 0 mod 2 and reject if it is 1 mod 2. What happens
if instead of 2 we use $2^N$ where $N$ is large? If $x$ is in the language $L$,
then the number of accepting configurations is $\leq 2^{m-q} \pmod 2^N$. If $x$
is not in $L$ then the number of accepting configurations is between $2^m -
2^{m-q}$ and $2^m \pmod 2^N$.
Unfortunately, we can't actually do this. However, we can accept if the number
of accepting configurations is 0 mod 2 and reject if it is -1 mod 2. This will
leave the intervals disjoint, which is sufficient for us.
\subsection{Arithmetic with Counting Functions}
$f: \Sigma^* \rightarrow \mathbb{Z}$ is a counting function if $\exists M \in
P$ such that $f(x) = \#$ y's such that $M(x, y) =1 $.
We show that if $f_1$ and $f_2$ are counting functions, then so are $f_1 \cdotp
f_2$ and $f_1 + f_2$. This is easy to see. To get a TM that that accepts $f_1
\cdotp f_2$ things given a TM $M_1$ that accepts $f_1$ things and a
TM $M_2$ that accepts $f_2$ things we simply put the two ``in series''. That
is, for branch of $M_1$ that accepts, we then run the the machine $M_2$ on $x$.
To get a TM that accepts $f_1 + f_2$ things, we flip a coin. depending on the
result of the coin flip, we either run $M_1$ or $M_2$.
$h: \mathbb{Z} \rightarrow \mathbb{Z}$ is a polynomial with non-negative
coefficients. If $f$ is a counting function, clearly so is $h(f)$ by the above.
We come up with a clever polynomial $h = 3f^4 + 4f^3$. If $f$ has 0 accepting
configurations modulo $2^k$ then $h(f)$ will have 0 accepting configurations modulo
$2^{2k}$. Moreover, if $f$ has 1 accepting configuration modulo $2^k$ then $h$
will have $-1$ accepting configurations modulo $2^{2k}$.
We then need to apply the process log $n$ times in order to actually get
something with the correct properties modulo $2^N$ (which we can actually do in
the correct time bound).
Reference the slides to see how to come up with the polynomial $h(f)$ that
works.
\end{document}