%&LATEX (tells OzTeX to use LaTeX.fmt)
\documentclass{article}
\input{preamble.tex}

\def\setof#1{\left\{ #1\right\}}
\def\sizeof#1{\left| #1\right|}
\def\Sizeof#1{\Big| #1 \Big|}


\newcommand{\dotp}[2]{\ensuremath{#1 \cdot #2}}
\newcommand{\vz}{\ensuremath{\vec{v_{0}}}}
\newcommand{\vo}{\ensuremath{\vec{v_{1}}}}
\newcommand{\vt}{\ensuremath{\vec{v_{2}}}}
\newcommand{\vN}{\ensuremath{\vec{v_{N}}}}
\newcommand{\X}{\ensuremath{\vec{X}}}
\newcommand{\xo}{\ensuremath{x_{1}}}
\newcommand{\xt}{\ensuremath{x_{2}}}
\renewcommand{\xi}{\ensuremath{x_{i}}}
\newcommand{\xj}{\ensuremath{x_{j}}}
\newcommand{\xN}{\ensuremath{x_{N}}}
\newcommand{\ro}{\ensuremath{r_{1}}}
\newcommand{\rt}{\ensuremath{r_{2}}}
\newcommand{\ri}{\ensuremath{r_{i}}}
\newcommand{\rj}{\ensuremath{r_{j}}}
\newcommand{\rn}{\ensuremath{r_{n}}}
\newcommand{\rM}{\ensuremath{r_{M}}}
\newcommand{\iz}{\ensuremath{i_{0}}}
\newcommand{\io}{\ensuremath{i_{1}}}
\newcommand{\ito}{\ensuremath{i_{2}}}
\newcommand{\ij}{\ensuremath{i_{j}}}
\newcommand{\iN}{\ensuremath{i_{n}}}
\newcommand{\Sa}{\ensuremath{S_{a}}}
\newcommand{\phiz}{\ensuremath{\phi_{0}}}
\newcommand{\phio}{\ensuremath{\phi_{1}}}
\newcommand{\phiN}{\ensuremath{\phi_{N}}}
\newcommand{\Prob}[1]{Pr\ensuremath{\left[ #1\right]}}
\newcommand{\0}{\ensuremath{\vec{0}}}
\newcommand{\bigo}{\ensuremath{\mathcal{O}}}
\newcommand{\Ebar}{\ensuremath{\overline{E}}}
\newcommand{\Tsat}{\ensuremath{\mathit{3\!-\!SAT}}}

\newcommand{\sigk}[2]{\ensuremath{\Sigma_{#1}#2}}
\newcommand{\pik}[2]{\ensuremath{\Pi_{#1}#2}}

\begin{document}


\lecture{10}{March 12, 1998}{Daniel A. Spielman}{Joshua A. Tauber}
 
\section*{Valiant and V. J. Vazirani (cont.)}

Consider a set $S \subseteq \{0, 1\}^{N}$, random vectors 
$\vz, \ldots \vN$, and the series of subsets: 
\begin{eqnarray*}
\sigma_{1} & = & \{\sigma \in S \mid \dotp{\vz}{\sigma} = 0 \} \\
\sigma_{2} & = &\{\sigma \in S \mid (\dotp{\vz}{\sigma} = 0) 
 \wedge (\dotp{\vo}{\sigma} = 0) \} \\
 & \vdots \\
\sigma_{N} & = &\{\sigma \in S \mid (\dotp{\vz}{\sigma} = 0)
  \wedge (\dotp{\vo}{\sigma} = 0) \wedge 
  \ldots \wedge (\dotp{\vN}{\sigma} = 0) \}
\end{eqnarray*}
where all operations are mod 2.  Last time we proved: 
\begin{fact}
\label{set}
If $\mid \!S \!\mid\ \geq 1$ then $\Prob{\exists ! i \mbox{
  such that} \mid\!\sigma_{i}\! \mid = 1} \geq  \frac{1}{8}$
\end{fact}

Let $\phi$ be a boolean formula in 3-CNF form over $N$ boolean 
variables 
$(\xo, \xt, \ldots, \xN)$.  We may elect to treat these variables as 
a vector, $\X$.
Choose $N+1$ random vectors of length $N: \vz, \vo, \ldots , \vN$.  
We define
\begin{eqnarray*}
\phiz & = & \phi \wedge (\dotp{\vz}{\X} = 0) \\
\phio & = & \phi \wedge (\dotp{\vz}{\X} = 0) \wedge (\dotp{\vo}{\X} = 
0) \\
      &   & \vdots \\
\phiN & = & \phi \wedge (\dotp{\vz}{\X} = 0) \wedge (\dotp{\vo}{\X} = 
0) \wedge \ldots \wedge (\dotp{\vN}{\X} = 0)
\end{eqnarray*}

\begin{observation}
Using Fact \ref{set} we observe that:
\begin{itemize}
\item If $\phi$ is \emph{not} satisfiable then neither are
  any of $\phiz, 
\phio, \ldots,\mbox{ {\rm }} \phiN$.
\item If $\phi$ \emph{is} satisfiable 
$\Prob{\exists{i} \mid \phi_{i}\ \mathrm{has\ exactly\ one\ 
statisfying\ assignment}} \geq \frac{1}{8}$
\end{itemize}
\end{observation}

\begin{claim}
\label{3-SAT}
$\phi_{i}$ can be transformed into a 3-CNF that is true IFF $\phi_{i}$ is 
true.
\end{claim}
Now we have a randomized production from $\Tsat$ to $N$ instances of 
$\Tsat$ such that 
\begin{itemize}
\item If the original $\Tsat$ instance is false then all $N$ are false.
\item If the original $\Tsat$ instance is satisfiable then 
\[\Prob{\mathrm{One\ of\ these\ instances\ is\ satisfied\ by\ 
exactly\ one\ assignment}} \geq \frac{1}{8}\]
\end{itemize}

Finally, we state our findings in the form we find most interesting:

\fbox{
\begin{minipage}{\textwidth}
\begin{theorem}
If there exists a randomized, polynomial time Turing machine, M, such 
that on input $w$
\begin{itemize}
\item M rejects $w$ if $w$ is a boolean formula in 3-CNF that is 
\emph{not} satisfiable.
\item if $w$ is a boolean formula in 3-CNF that has 
exactly one satisfying assignment, then $\Pr{M \mbox{ accepts
  } w} \geq 1/2$.
\item M may accept or reject \emph{arbitrarily} otherwise.
\end{itemize} 
then $NP = RP$.
\end{theorem}
\end{minipage}
}

\begin{observation}
M accepts $w \Rightarrow w \in SAT$.  In other words, M has 
zero-sided error.  That is the key to getting a language in $RP$.
\end{observation}

\begin{proof}
\begin{description}
\item [$\supseteq$] Obvious.
\item [$\subseteq$]
Given $M$, we construct another randomized polynomial time TM, $M'$, such 
that $L(M') = \Tsat$. On input $w$, $M'$ uses random bits to 
construct $N+1$ new instances of $\Tsat$ (as in Claim \ref{3-SAT}) and 
runs $M$ on all $N+1$ instances.  $M'$ accepts if $M$ accepts any of them.
If $w \in \Tsat$ then $\Prob{M'\mathrm{\ accepts\ some\ instance}} \geq
\frac{1}{16}$.  If not then $\Prob{M'\mathrm{\ rejects}} = 1$.  Thus,
$L(M')$ is $RP$ version of $\Tsat$.
\end{description}
\end{proof}

\begin{corollary}
The existence of M implies collapse of the polynomial hierarchy.
\end{corollary}

\begin{proof}
We know that $RP \subseteq P/poly$.  Therefore, $NP = RP \Rightarrow NP \subseteq P/poly \Rightarrow \sigk{2}{P} = 
\pik{2}P$
\end{proof}

\section*{Randomized Boolean Polynomials}

The previous result says something fundamental about the OR ($\bigvee$) 
function.  Somehow, the addition of random bits makes $\bigvee$ 
equivalent to $\exists !$.  Next we pursue this idea further by 
considering boolean formulas in the form of randomized polynomials over 
the real numbers, $\mathbf{R}$.  (Or polynomials interpreted as boolean 
formulas.)

Let
\begin{eqnarray*}
TRUE & \equiv & 1 \\
FALSE & \equiv & 0 \\
\bigwedge(\xo,\ldots, \xN) & \equiv & \sum_{i=1}^{N}\xi \\
\bigvee(\xo,\ldots, \xN) & \equiv & 1 - \sum_{i=1}^{N}(1 - \xi) \\
\neg(x) & \equiv & 1 - x 
\end{eqnarray*}

\subsection*{Degree of non-randomized boolean polynomials}
Notice that the $AND$ and $OR$ polynomials given have degree $N$.

\begin{claim}
Any polynomial function for $AND$ over $\{0,1\}^N$ will have degree 
at least $N$. .
\end{claim}

\begin{proof}
Given that $x \in \{0,1\}$, no variable will occur with degree $>1$
since $x = x^2$.
Furthermore, AND functions of subsets of $xi$'s form a  basis of all 
functions over $\{0,1\}^N$.  Consider the matrix of AND functions of
subsets of $\{0,1\}^N$.

\[
\begin{array}{cc}
& \overbrace{
\begin{array}{ccccccccc}
\{\xo\} & \ldots & \{\xN\} & 
\{\xo,\xt\} & \ldots & \{\xo,\xN\} & \ldots & 
\{\xo,\ldots,\xN\} 
\end{array}
}^{\mathrm{Index\ with\ all\ members\ of\ the\ power\ set\ of\ 
}\{0,1\}^N}\\
\begin{array}{c} 
\scriptstyle{\mathrm{Index\ with}} \\ 
\scriptstyle{\mathrm{all\ possible}} \\
\scriptstyle{\mathrm{assignments}} \\
\scriptstyle{\mathrm{to\ }\{0,1\}^N}
\end{array}
\left\{
\begin{array}{c} 
\{0, \ldots, 0\} \\
\{0, \ldots, 1\} \\
\vdots \\
\{1, \ldots, 1\}
\end{array} 
\right. & 
\left(
\begin{array}{c} 
\\
\mathrm{Value\ of\ entry \ }(i,j) = AND(j^{th} subset) \mathrm{\ 
with\ } i^{th} {\ assignment.} \\
\\
\\
\end{array}
\right)

\end{array}
\] 
We leave it as an exercise to the reader to show that the matrix thus 
formed (with proper ordering of the indices) is an upper triangular 
matrix.  Thus, the AND functions are linearly independent, forming 
the needed basis.
\end{proof}

\subsection*{A Randomized Polynomial for Approximating OR}

While we cannot find a lower degree deterministic polynomial for $AND$ 
(or $OR$), we can do better with the addition of random bits.
We will use Fact \ref{set} show how to make a randomized polynomial 
$P(\xo, \ldots, \xN,\ro, \ldots, \rM)$ 
where $x_{i}, r_{i} \in \{0,1\}$ such that 
\begin{itemize}
\item P has degree $\bigo(log^{2}N)$.
\item P uses $\bigo(log^{2}N)$ random bits.
\item If $\bigvee^{N}_{i=1}\xi = 0$ then for all possible assignments to 
$(\ro,\ldots, \rM), P(\xo, \ldots, \xN, \ro, \ldots, \rM) = 0$. 
\item If $\bigvee^{N}_{i=1}\xi = 1$ then for at least $\frac{1}{8}$ of 
possible assignments to $(\ro, \ldots, \rM), 
P(\xo, \ldots, \xN, \ro, \ldots, \rM) = 1$.
\item Otherwise, the value of $P(\xo, \ldots, \xN, \ro, \ldots, \rM)$ 
is arbitrary and, in particular need not be $\in \{0,1\}$.
\end{itemize}

Let $n = \lceil \log N \rceil$.
We will write index $1 \leq i \leq N$ in binary as $\io \ito \ldots \ij 
\ldots \iN$.  That is, we can treat each index $i$ as a binary vector 
of length $n$.  Similarly, $(\ri, \ldots, \rM)$ will be interpreted 
as giving $n+1$ binary vectors of length n.  Thus, $M = n(n+1)$.

Note: If at most one of $\xo, \ldots, \xN = 1$ then 
$\bigvee^{N}_{i=1}(\xi) = \sum^{N}_{i=1}(\xi)$. 

\subsubsection*{Parity Polynomial}

As a step to writing $P$, we define a polynomial that computes the inner 
product of index $i$ (taken as a vector) and a corresponding vector of 
random bits.  Since all operations are mod 2, this calculation reduces 
to simply computing the parity of the individual terms of the inner 
product.

We simplify further by transforming our basis so that $TRUE \equiv -1$ 
and $FALSE \equiv 1$.  Under this basis, parity is simply the product 
of terms.  The transformation is a simple linear one:
 
\begin{eqnarray*}
FALSE \equiv 0
\stackrel{y = 1-2x}{\longrightarrow}
FALSE \equiv 1 \\
TRUE  \equiv 1
\stackrel{y = 1-2x}{\longrightarrow}
TRUE  \equiv -1
\end{eqnarray*}

(The inverse of this transformation is $x = \frac{1}{2}(1-y)$.)
So, we define the parity polynomial $E$:

\begin{eqnarray*}
E(\io, \ldots, \iN, \ro, \ldots, \rn) & = & \dotp{\vec{\imath}}{\vec{r}} \bmod 2 \\ 
& = & Parity(\io\ro, \ito\rt, \ldots, \iN\rn)  \\
& = & \prod^{n}_{j=1}(1-2\ij\rj) \\
\end{eqnarray*} 

Transforming $E$ back to our original basis yields: 

\[
E = \frac{1}{2}
\left[ 1 - \prod^{n}_{j=1}(1 - 2 \ij \rj) 
\right]
\]

As it turns out, we are more interested in $\Ebar = 1 - E$.
Multiplying $\xi$ by $\Ebar$ can be used to select $\xi$ such that 
$\dotp{\vec{\imath}}{\vec{r}} = 0$.  Thus, 

\begin{eqnarray*}
\sum_{\dotp{\vec{\imath}}{(\ro \ldots \rn)} = 0}\xi & = & 
  \sum_{i=1}^{N}\xi\Ebar_{i} \\
& = & \sum_{i=1}^{N}\xi \left[1 - \frac{1}{2} \left( 1 - \prod^{n}_{j=1}(1 - 2 \ij \rj) \right) \right]
\end{eqnarray*}

\subsubsection*{$\Sa$ Polynomial}

We can now use $\Ebar$ to construct $P$.
But first, for ease of notation, lets renumber $P$'s random bits,
$\ri$, as $n+1$ vectors.
\[
\begin{array}{ccccc}
\left(
\begin{array}{ccc}
\ro & \ldots & \rn \\
r_{n+1} & \ldots & r_{2n} \\
& \vdots & \\
r_{n^{2}+1} & \ldots & \rM
\end{array}
\right)
& \longrightarrow &
\left(
\begin{array}{ccc}
\ro^{1} & \dots & \rn^{1} \\
\ro^{2} & \dots & \rn^{2} \\
& \vdots & \\
\ro^{n+1} & \dots & \rn^{n+1}
\end{array}
\right)
& = &
\left(
\begin{array}{c}
\vec{r}^{1} \\
\vec{r}^{2} \\
\vdots    \\
\vec{r}^{{n+1}}
\end{array}
\right)
\end{array}
\]

Using this renumbering with the parity polynomial yields:
\begin{eqnarray*}
\dotp{\vec{\imath}}{\vec{r}^{k}} = 0 & \Leftrightarrow & \Ebar_{i,k} = 1 \\
(\dotp{\vec{\imath}}{\vec{r}^{1}} = 0) \wedge 
(\dotp{\vec{\imath}}{\vec{r}^{2}} = 0) \wedge \ldots \wedge
(\dotp{\vec{\imath}}{\vec{r}^{a}} = 0)
& \Leftrightarrow & \prod_{k=1}^{a} \Ebar_{i,k} = 1 
\end{eqnarray*}


We now define polynomial $\Sa$.
\begin{eqnarray*}
\stackrel{\displaystyle{\Sa}}{\scriptstyle{1 \leq a \leq n+1}} &
 = &\sum_{i=1}^{N} \left[ x_{i} \prod_{k=1}^{a} \Ebar_{i,k} \right]\\
& = &\sum_{i=1}^{N}
\left[ x_{i} \prod_{k=1}^{a} 
\left[ 1 - \frac{1}{2} 
\left[ 1 - \prod_{j=1}^{n}(1 - 2 \ij r^{k}_{j} )
\right]
\right]
\right]
\end{eqnarray*}

We know that $\bigvee^{N}_{i=1}(\xi) = 0 \Rightarrow \Sa = 0.$ 
Otherwise, $Pr[\mathrm{some\ \Sa} = 1] \geq \frac{1}{8}$ over the 
choice of random bits.  One way to look at $\Sa$ is that $\Sa$ is the 
number of true valued $\xi$ that remain after restricting the $OR$ 
with $a$ random, linear restrictions.

\center{[We will finish next time . . .]}
\end{document}