\documentclass[10pt]{article}
\usepackage{amsfonts}
\newtheorem{define}{Definition}
\newtheorem{lem}{Lemma}
\newtheorem{cor}{Corollary}

%\newcommand{\Z}{{\bf Z}}
\usepackage{psfig}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in
%useful shortcuts:
\newcommand{\usat}{Unique\textrm{-}SAT}
\begin{document}
\input{preamble.tex}

\lecture{12}{
March 19,
2007}{Madhu Sudan}
{
% The
Suho Oh, Jose Soto}


\section {Overview}
\begin{itemize}
\item Randomized Reductions. Valiant-Vazirani: $SAT \leq_{RP} \usat$.
\item Toda's Theorem: $PH \subseteq P^{\#P}$.
\end{itemize}

\section{The Theorem of Valiant-Vazirani.}
To state this theorem we will need some definitions first:
\begin{define}[$\usat$ promise problem].
\begin{eqnarray*}
 \usat &=& (U_{YES}, U_{NO}).\\
 U_{YES} &=& \{\varphi \,\vert\, \varphi \textrm{ has 1 satisfying assignment}\}.\\
 U_{NO} &=& \{\varphi \,\vert\, \varphi \textrm{ has 0 satisfying assignment}\}.
 \end{eqnarray*}
\end{define}

\begin{define}[Randomized Reductions]
Given two promise problems $\Pi = (\Pi_{YES},\Pi_{NO})$ and $\Gamma = (\Gamma_{YES}, \Gamma_{NO})$. We say that $\Pi$ reduces to $\Gamma$ under a $BP$ randomized reduction ``$\Pi \leq_{BP} \Gamma$" if there exists a probabilistic polynomial time algorithm $A$, a polynomial $p(n)$ and a polynomial time computable function $s(n)$ such that:
\begin{eqnarray*}
x \in \Pi_{YES} \Longrightarrow &A(x) \in \Gamma_{YES} &\textrm{ w.p. } \geq s(n) + \frac{1}{p(n)}.\\
x \in \Pi_{NO} \Longrightarrow &A(x) \not\in \Gamma_{NO} &\textrm{ w.p. } \leq s(n).\\
&[\Longleftrightarrow \textrm{$A(x) \in \Gamma_{NO}$} &\textrm{ w.p. $\geq 1-s(n)$}].
\end{eqnarray*} 
When $s(n)=0$ we say that it is a $RP$ randomized reduction and we denote it by ``$\Pi \leq_{RP} \Gamma$".
\end{define}
Using the previous definition we can state the theorem as follows:
\begin{theorem}[Valiant-Vazirani]
 $$SAT \leq_{RP} \usat.$$
\end{theorem}

To find an $RP$ reduction a natural idea is to map an instance $\varphi(x)$ of $SAT$ into a new formula $\psi(x) = \varphi(x) \wedge f(x)$, where $f(x)$ is a sufficiently ``nice'' formula. In that way if $\varphi(x) \in SAT_{NO}$ then we would know that $\psi(x)$ has no satisfying assignment, and so $\psi(x) \in U_{NO}$. The problem is to determine a nice $f(x)$ such that if $\varphi \in SAT_{YES}$, then $\psi(x)$ has exactly one satisfying assignment with enough probability.

How can we find such a formula?
 
One idea is to pick some $m \leq n$, and some $h: \{0,1\}^n \to \{0,1\}^m$ ``at random'', and output the formula $\psi(x) = \varphi(x) \wedge [h(x) = \overline{0}]$ so that if $\varphi \in SAT_{YES}$ then hopefully $\psi \in U_{YES}$.

Let us formalize the idea a little bit:
 
Define for a fixed $\varphi$, the set $S$ of satifying assignment of $\varphi$, $S=\{x \,\vert\, \varphi(x) = 1\}$. Clearly there exist an $m\in\{2,\ldots,n+1\}$ such that $2^{m-2} \leq |S| \leq 2^{m-1}$. Using that $m$ we can pick a function $h: \{0,1\}^n \to \{0,1\}^m$ and use it to output $\psi$.

How can we find the right $m$? We just guess it, since we are picking it at random from the set $\{2,\ldots, n+1\}$, we are right with probability $1/n$.

How can we pick $h$? We can not pick it at random since $h$ would not be efficiently computable. What do we mean/want? 

We need a set $\mathcal{H} \subseteq \{ h: \{0,1\}^n \to \{0,1\}^m\}$ such that:
\begin{enumerate}
 \item $\mathcal{H}$ is not too big. Precisely we need $|\mathcal{H}| \leq 2^{poly(n)}$ so that we are able to pick an element from it using with only $poly(n)$ random bits.
 \item Every $h \in \mathcal{H}$ should be computable in polynomial time (i.e. it should have a small formula)
 \item A typical $h \in \mathcal{H}$ should be sufficiently random. More precisely, for any set $S \subseteq \{0,1\}^n$ with $2^{m-2} \leq |S| \leq 2^{m-1}$,
 $$Pr[\exists ! x\in S \textrm{ s.t. } h(x) =\overline{0}] \geq \Omega(1).$$
\end{enumerate} 
 How can we get such family? We can use a ``Pairwise Independent hash family''.

\begin{define}[Pairwise independent]
 $\mathcal{H} \subseteq \{h: \{0,1\}^n \to \{0,1\}^m\}$ is a pairwise independent family if
$\forall x \neq y \in \{0,1\}^n, \forall \alpha,\beta \in \{0,1\}^m$,
$$\Pr_{h\in\mathcal{H}}[h(x) = \alpha, h(y)=\beta] = \frac{1}{4^m}.$$
\end{define}

\begin{lem} There exists a pairwise independent hash family $\mathcal{H}$ such that it is easy to sample and $\forall h \in \mathcal{H}$, formula-size$(h)$ is $poly(n)$.
\end{lem}
\begin{proof}
Define $$\mathcal{H} = \{ h_{A,b}(x) = A x + b \textrm{ (mod 2)} \,\vert\, A \in \{0,1\}^{m\times n}, b\in \{0,1\}^m\}.$$
It is clear that $h_{A,b}$ has small formula size and for any $x\neq y, \alpha,\beta$:
$$\Pr_{A,b}[Ax + b = \alpha, Ay + b = \beta] = \frac{1}{4^m}.$$
\end{proof}

\begin{lem} $\forall S \subseteq \{0,1\}^n$, $2^{m-2} \leq |S| \leq 2^{m-1}$,
$$\Pr_{h\in\mathcal{H}}[\exists! x \in S, h(x) = \overline{0}]\geq \frac{1}{8}.$$
\end{lem}
\begin{proof}
Fix $x\in S$, then:
$$\Pr_{h\in\mathcal{H}}[h(x)=0]=\frac{1}{2^m}.$$
Fix $x\neq y\in S$, then:
$$\Pr_{h\in\mathcal{H}}[h(x)=0 \wedge h(y)=0]=\frac{1}{4^m}.$$
Then:
\begin{eqnarray*}
\Pr_{h\in\mathcal{H}}[h(x)=0 \wedge \forall y \in S\setminus \{x\}, (h(y) \neq 0)] &\geq& \Pr_{h\in\mathcal{H}}[h(x)=0]-\sum_{y\in S\setminus\{x\}}\Pr_{h\in\mathcal{H}}[h(x)=0=h(y)]\\
&\geq& \frac{1}{2^m}-\frac{|S|}{4^m} \geq \frac{1}{2^{m+1}},
\end{eqnarray*}
where the last inequality holds since $|S|\leq 2^{m-1}$.

Hence,
\begin{eqnarray*}
\Pr_{h\in\mathcal{H}}[\exists x \in S \textrm{ s.t. } h(x)=0 \wedge \forall y \in S\setminus \{x\}, (h(y) \neq 0)] &=& \sum_{x\in S}\Pr_{h\in\mathcal{H}}[h(x)=0 \wedge \forall y \in S\setminus \{x\}, (h(y) \neq 0)]\\
&\geq& \frac{|S|}{2^{m-1}}\geq \frac{1}{8},
\end{eqnarray*}
where the first equality holds by independence of the events inside the probability, and the last equality holds since $|S| \geq 2^{m-2}$.
\end{proof}

Using both lemmas we can prove Valiant-Vazirani's theorem. Given an instance $\varphi$ for $SAT$, the polynomial time algorithm $A$ does the following:
\begin{enumerate}
\item It picks at random $m \in \{2,\ldots,n+1\}$.
\item It picks at random a hash function from the hash family $\mathcal{H}$ given by Lemma 1.
\item It outputs the formula $\psi(x) = \varphi(x) \wedge [h(x)=0]$.
\end{enumerate}
If $\varphi(x) \in SAT_{YES}$, then with probability $1/n$, $A$ picks the right $m$. Using Lemma 2 for $S$ the set of satisfying assignments of $\varphi$, we know that $A$ picks a hash function from $\mathcal{H}$, such that $h(x)=0$ for an unique $x \in S$. It follows that with probability $1/(8n)$ the algorithm outputs a formula with only one satisfying assignment, i.e. a formula in $U_{YES}$.

On the other hand, if $\varphi(x) \in SAT_{NO}$, then $A$ will output $\psi(x)$ that has no satisfying assignment. 
Hence $A$ is an $RP$ reduction from $SAT$ to $\usat$.

\subsection{Consequences}
\begin{cor} $SAT \leq_{RP} \bigoplus SAT$. \\
Where $\bigoplus SAT := \{\phi\ | $ Number of satisfying assignments of $\phi$ is even $\}$ 
\end{cor}
\begin{proof}\\
We reduce $\usat$ to $\bigoplus SAT$ as following. For given $\psi(x) \in \usat$,


$$\psi^{'}(bx) :=\left\{\begin{array}{cl}
       1, & b=0,x=\overline{0} \\
       1, & b=1,\psi(x)=1 \\
       0, & o.w.
          \end{array}\right.$$	   

Combining with $SAT \leq_{RP} \usat$, the corollary follows!
\end{proof}

Now we can use this reduction $k$ times to get,
\begin{eqnarray*}
  \psi &\longrightarrow& \psi_1(x_1)\\
   &\longrightarrow& \psi_2(x_2)\\
   &\longrightarrow& \psi_3(x_3)\\
   &\cdot \cdot \cdot& \\
   &\longrightarrow& \psi_k(x_k).
\end{eqnarray*}
Set $\hat{\psi}$ as, 
$$
\hat{\psi}(x_1, \cdot\cdot\cdot, x_k) = \bigwedge_{i=1}^k \psi_i(x_i)
$$
Then, $\#$ of satisfying assignments of $\hat{\psi}$ $= \prod({\# \textrm{of satisfying assignments of $\psi_i$}})$
\\
So if the $\#$ of satisfying assignments for some $\psi_i$ is even, then $\#$ of satisfying assignments for $\hat{\psi}$ is even too! From this we get :
$$
SAT \leq_{StrongBP} \bigoplus SAT
$$

\section {Toda's Theorem}

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

\subsection{Operators}
For a complexity class $\mathcal{C}$, define the following operators:
\\

Parity Operator :
\begin{itemize}

\item $\bigoplus \mathcal{C} := \{\bigoplus L | L \in \mathcal{C} \}$
\item $\bigoplus L := \{ x | \#$ of $y$'s satisfying $(x,y) \in L$ is even $\}$

\end{itemize}

BP Operator :
\begin{itemize}
\item $BP \cdot \mathcal{C} := \{BP \cdot L | L \in \mathcal{C} \}$
\item $BP \cdot L := \{x |\  Pr_y [(x,y) \in L ] \geq 1 - 2^{-q(n)} \}$ 
\item i.e., if $x\not \in BP \cdot L$,  $Pr_y[(x,y) \in L] \leq 2^{-q(n)}$
\end{itemize}

$\exists$ Operator :
\begin{itemize}
\item $\exists \mathcal{C} := \{\exists L | L \in \mathcal{C} \}$
\item $\exists L := \{ x | \exists y$ such that $ (x,y) \in L \}$.
\end{itemize}

\subsection{Properties}
 Proofs will be shown on Wednesday.
\begin{enumerate}
 \item $\bigoplus \cdot P \cdot \mathcal{C} \leq BP \cdot \bigoplus  \mathcal{C}$.
 \item $\bigoplus \cdot \bigoplus \cdot \mathcal{C} \leq \bigoplus  \mathcal{C} $.
 \item $BP \cdot BP \cdot \mathcal{C} \leq BP \cdot \mathcal{C}$.
\end{enumerate}


\subsection{Main Ideas}
 $SAT \leq_{StrongBP} \bigoplus SAT$ implies:
 \begin{itemize}
 \item $NP \subseteq BP \cdot \bigoplus \cdot P$.
 \item $Co$-$NP \subseteq BP \cdot \bigoplus \cdot P$ , because $BP \cdot \bigoplus \cdot P$ is closed under complement.
\begin{eqnarray*}
\Sigma_{2}^{P} \subseteq \exists \cdot \forall \cdot P &\subseteq& BP \cdot \bigoplus \cdot BP \cdot \bigoplus \cdot P \\
&\subseteq& BP \cdot BP \cdot \bigoplus \cdot \bigoplus \cdot P \textrm{  (Using properties above)}\\ &\subseteq& BP \cdot \bigoplus \cdot P.
\end{eqnarray*}
\end{itemize}
By induction, we can get
$$
\Sigma_{k}^{P} \subseteq BP \cdot \bigoplus \cdot P.
$$
which implies $PH \subseteq BP \cdot \bigoplus \cdot P$.

\section{To show Next time}

\begin{itemize}
\item $BP \cdot \bigoplus \cdot P \subseteq P^{\#P}$.
\item $L:=\{(M,x,a,b)| \#\ \{y|M(x,y)$ accepts $\} \leq a(mod\ b)$ \} $\in P^{\#P}$.
\item $\Sigma_k^{P} \subseteq \exists \cdot BP \cdot \bigoplus \cdot P$.
\end{itemize}


\end{document}