\input{preamble}
\begin{document}
\lecture{Derandomizing $\AM$: Miltersen-Vinodchandran}{Pseudorandomness}{Srikanth Srinivasan}{Ramprasad Saptharishi}

\section{Motivation}

In the last pseudorandomness meeting, we looked at the
Impagliazzo-Wigderson theorem. The theorem said that if you have a
worst-case hard function in $\E$, then you can use that to construct a
pseudorandom generator to derandomize $\BPP$. Today, we shall look at
the non-deterministic analogue of that theorem. 

In order to address the notion of a 'probabilistic version of $\NP$',
we need to define the classes. 

\begin{definition}
  A language $L\in \AM$ if there exists a polynomial time predicate
  $R$ such that:
  \begin{eqnarray*}
    x\in \L & \implies & \Pr_y\insquar{\exists z : R(x,y,z)} \geq
    \frac{3}{4}\\
    x\notin \L & \implies & \Pr_y\insquar{\exists z : R(x,y,z)} <  
    \frac{1}{4}
  \end{eqnarray*}

  Similarly, a language $L\in \MA$ if there exists a polynomial time predicate
  $R$ such that:
  \begin{eqnarray*}
    x\in \L & \implies & \exists z : \Pr_y\insquar{R(x,y,z)} \geq
    \frac{3}{4}\\
    x\notin \L & \implies & \forall z : \Pr_y\insquar{R(x,y,z)} <  
    \frac{1}{4}
  \end{eqnarray*}
  Of course, $y$ and $z$ are polynomially bounded in the length of
  $x$.
\end{definition}

It is well known that $\MA\subseteq AM$ (if the reader does not know
the proof, he should try and work it out. It uses some simple Hashing
lemmas that you would have probably seen earlier).

There is a communcation protocol that makes the class more
natural. Arthur is a king, with computational power of just a
randomized polynomial time machine. Merlin, a courtier, is all
powerful. Arthur needs to check if a certain $x$ is in the
language. 

In $\AM$, Arthur sends Merlin $y$ and Merlin replies with $z$ after
which Arthur checks some predicate. What the definition of $\AM$ says
is that if $x\in L$, then for most of Arthur's $y$'s, Merlin can
convince Arthur. And on the other hand, if $x\notin L$, Merlin can't
cheat much. 

The class $\MA$ is a similar protocol where Merlin first sends a $y$
and Arthur does some randomized computation using bits $z$. 

One could look at $\BP$ and $\exists$ as just operators on a class and
say:
\begin{eqnarray*}
\AM & = & \BP\cdot\exists\cdot\P\\
\MA & = & \exists\cdot\BP\cdot\P\\
\end{eqnarray*}

We want to prove the following:
\begin{theorem}(sketch) 
If there exists a $f\in \NE\intersection \coNE$ with ``large
nondeterministic circuit complexity'', then $\AM = \NP$.
\end{theorem}

One important fact of $\AM$ is that one could equivalently change the
conditions to one of perfect completeness:
\begin{eqnarray*}
  x\in \L & \implies & \Pr_y\insquar{\exists z : R(x,y,z)} = 1\\
  x\notin \L & \implies & \Pr_y\insquar{\exists z : R(x,y,z)} <  
  \frac{1}{2}
\end{eqnarray*}
And of course, one could just negate both the conditions and say:
\begin{eqnarray*}
  \Pr_y\insquar{\exists z : R(x,y,z)} \geq \frac{1}{2} &\implies& x\in L\\
  \Pr_y\insquar{\exists z : R(x,y,z)} = 0& \implies &x\notin L
\end{eqnarray*}

To check something of this kind, we need \emph{Hitting Set
  Generators}.

\section{Hitting Set Generators}

Let us look at any $\RP$ algorithm. This has the property that if
$x\in L$, then it accepts on all its inputs. And if $x\notin L$, then
it rejects at least half the inputs. Therefore, in order to find out
of $x\in L$, all we need to do is find one random string on which the
algorithm rejects. 

Negating this notion, we are given an algorithm that either rejects
all inputs or accepts at least half the inputs. We need to distinguish
between these two cases. This is the motivation of \emph{Hitting Set
  Generators}.

\begin{definition}
  A hitting set generator for a class $C$ of circuits of size $s$ is a
  function $G$ that produces a set $S$ of strings in $\zo^n$ such that
  any circuit that accepts at least a $\frac{1}{2}$ fraction its
  inputs will accept something from $S$. And further, $|S| =
  \poly(s)$.

  The parameter $\frac{1}{2}$ is called the threshold of the HSG. One
  could talk of arbitrary threshold HSGs as well. 
\end{definition}

Thus for $\RP$, given an input $x$ we can produce a circuit $C_x$ that
either none or accepts at least half of them. If we have an explicit
HSG, then we can just run this circuit over all elements of the HSG
and check for it. 

In our case, we need a notion of non-determinstic circuits. The
definition of hitting set generators for this class is identical. 


\section{Non-Deterministic Circuits}

\begin{definition}
  A non-determinstic circuit $C$ is one that has two inputs, one say
  $x$ and another auxillary input $y$. We say that $C$ ``accepts'' $x$
  non-determinstically if there exists a $y$ such that $C(x,y) =
  1$. Of course, $|y|$ is polynomial in $|x|$. 
\end{definition}
The class of non-deterministic polynomial sized circuits is
$\NP/\poly$. Similarly, we can define co-nondeterministic
circuits. Now we need a notion of non-uniform analogues of
$\NP\intersection \coNP$. The following definition captures that.

\begin{definition}
  A single-valued non-deterministic circuit is a non-deterministic
  circuit $C$ with two output bits, one the normal output and another
  flag bit. The flag bit indicates that the output bit is indeed the
  right output. More formally, 
  \begin{eqnarray*}
    x\in L  & = & \exists y : \text{flag $= 1$ and output $= 1$}\\
    x\notin L & = & \exists y : \text{flag $= 1$ and output $= 0$}
  \end{eqnarray*}
\end{definition}
The class of polynomial sized SV non-deterministic circuits captures
$\NP\intersection \coNP / \poly$. 


With the definitions in place, we can now state the theorem
precisely. 

\begin{theorem}
  If  there exists $f\in \NE\intersection \coNE$ such that it cannot be
  computed by SV non-deterministic circuits of size $2^{n^\epsilon}$
  for some $\epsilon > 0$, then $\AM = \NP$. 
\end{theorem}

Now let us get back to $\AM$ and express in terms of circuits. By the
definition, given an input $x$, we can construct a non-deterministic
circuit $C$ such that it either accepts at least half its inputs or
rejects all of them (inputs being the random bits here, and Merlin's
reply being the auxillary input). Therefore, if we have a HSG with
threshold $\frac{1}{2}$ for co-nondeterministic circuits, then $\AM =
\NP$. 

The proof will proceed through two lemmas:
\begin{enumerate}
\item Disperser Lemma: If there are HSGs with certain
  thresholds, then we can use that to create a HSG with threshold
  $\frac{1}{2}$. 
\item Main Lemma: If we have a hard function, then we can use that to
  construct HSGs of the certain threshold we are looking for.
\end{enumerate}

\section{Proofs}

And as the name suggests, the Disperser Lemma uses these objects
called Dispersers. Let us first define them.

\begin{definition}
  A family of bipartite graphs is said to be an $(\epsilon,\delta)$
  disperser family if
  \begin{itemize}
  \item $U_n = \zo^n$
  \item $V_n = \zo^{n^\delta}$
  \item For any subset $S$ of vertices of $U_n$ such that $|S| \geq
    2^{n^\epsilon}$, then $\abs{N(s)} \geq \abs{V_n}/2$. 
  \end{itemize}
  The disperser family is said to be explicit if there is a polynomial
  time algorithm that on input $u$ outputs $N(u)$. 
\end{definition}

We shall use the following theorem  as a blackbox but one could prove
it easily from Trevisan's Extractor. 

\begin{theorem}
  For every $\epsilon > 0$, there exists a $\delta > 0$ such that
  there is an explicit $(\epsilon,\delta)$ disperser family. 
\end{theorem}

But why dispersers? The reason is that it can be used to reduce the
error in randomized algorithms. We shall illustrate this through the
disperser lemma. 

\begin{lemma}[Disperser Lemma]
For every $\epsilon > 0$, there exists $q > 1$ and $\delta > 0$ such
that, if there is an explicit HSG for co-nondeterministic circuits of
size $n^q$ with threshold $1 - \frac{2^{n^\epsilon}}{2^n}$, then we
can construct explicit HSGs, outputs a set of strings of length
$n^\delta$, for size $n^\delta$ with threshold $\frac{1}{2}$.
\end{lemma}

The proof is simple, and we urge the reader to attempt it on his own
before reading the proof. 

\begin{proof}
Let $H \subset \zo^n$ be a hitting set with threshold $1
- \frac{2^{n^\epsilon}}{2^n}$. Thus, $H$ can be identified with a
subset of left vertices in an $(\epsilon,\delta)$ disperser. 

Let $H' = N(H)$. We claim that $H'$ is a hitting set with threshold
half for circuits of size $n^\delta$. Suppose not, then there exists
some circuit $C'$ of size $n^\delta$ that accepts more than half the
inputs but doesn't accept any string in $H'$. Now consider the
following circuit $C$: it takes an input $x\in \zo^n$, looks at $N(x)$
in the disperser, simulates $C'$ on all the neighbours and accepts if
and only if at least one of them is accepted by $C'$. 

Let $Z(C)$ denote the set of strings that evaluate to $0$ by $C$. By
assumption, $\abs{Z(C')} \leq \frac{\abs{V_n}}{2}$. Now look at
$Z(C)$, suppose $Z(C) > 2^{n^\epsilon}$ then $N(Z(C))
> \frac{\abs{V_n}}{2}$. Then, $N(Z(C))$ must intersect with
$V_n \backslash Z(C')$ which means that there is an edge $(x,y)$ such
that $C'(y) = 1$ which contradicts $x\in Z(C)$. Therefore,
$\abs{Z(C)}\leq \frac{2^{n^\epsilon}}{2^n}$. Also note that $C'$ does
not accept any string in $H$, which contradicts the assumption that
$H$ was a hitting set. 

One small subtlety, where did $q$ come into the picture? Note that we
need a bound on the size to say that something is a hitting set
generator of certain threshold. Therefore, all we need to ensure is
that $H$ is a hitting set for the above circuit. Since the disperser
is explicit, the running time of $C$ is bounded by some $n^q$. Choose
that $q$. 
\end{proof}

The motivation of dispersers comes from the fact that it allows us to
amplify the success probability without using too many random
bits. The error amplification was hidden in the above proof due to the
hitting sets though but it is very easy to see how dispersers achieve
it. Also note that repeated applications of the experiments, or random
expander walks will not give us such strong parameters. \\

Now for the main lemma. It has a lot of parameters, but bear with it
and we shall parse it after stating it. 

\begin{lemma}
For every $\epsilon > 0$ and $k \geq q \geq 1$, there is a polynomial
time function $\mathcal{H}$ that takes as input a function
$f:\zo^m\longrightarrow \zo$ and outputs a set of strings in
$\zo^n$. $\mathcal{H}$ further has the property that if $f$ has SV
non-deterministic circuit complexity at least $2^{cm\inparen{\epsilon
+ \frac{q}{k}}}$ for a constant $c$, then $\mathcal{H}(f)$ is a
hitting set generator for size $n^q$ co-nondeterministic circuits with
threshold $\inparen{1 - \frac{2^{n^\epsilon}}{2^n}}$. Here, $n =
(2m/k)2^{(2m/k)}$.
\end{lemma}

Note that $m$ is $O(\log n)$. What this says is that for every
$\epsilon > 0$, we can create a \emph{hitting set function generator}
that uses a ``hard'' truth-table to compute a hitting set generator of
certain threshold. The rest of the parameters are for the sizes
etc. Every variable other than $m,n$ are going to be constants. 

\begin{proof}
Fix a field $\F$ such that $\abs{\F} = 2^{2m/k}$, and identify it with
$\zo^{2m/k}$. And let $H\subseteq \F$ of size $2^{m/k}$ that is
identified with $\zo^{m/k}$. Therefore, $f$ can be thought of as a
function $f:H^k \longrightarrow \zo$. Now take the polynomial
extension of $f$, of degree less than $2^{m/k}$ in each variable which
can be computed to interpolation. Therefore, we have
\begin{eqnarray*}
\tilde{f}:\F^k& \longrightarrow & \zo\\
\tilde{f}\mid_{H^k} & = & f
\end{eqnarray*}

Given any $i\in [k]$ and ${\bf a} = \inparen{a_1,\cdots,
a_{i-1},a_{i+1},\cdots, a_k}\in \F^{k-1}$, define
$$
\alpha_x = f(a_1,a_2,\cdots, a_{i-1},x,a_{i+1},\cdots, a_k)
$$
And define vectors ${\bf v}(i,{\bf a})
= \inparen{\alpha_x}_{x\in \F}$. This is just the evaluation of $f$ in
the line $(a_1,a_2,\ldots, a_{i-1},\ \ \centerdot\ \ , a_{i+1},\ldots,
a_k)$. Note that $\abs{{\bf v}(i,{\bf a})} = (2m/k)2^{(2m/k)} = n$. We
now define the output of $\mathcal{H}$.

$$
\mathcal{H}(f) = H_f = \setdef{{\bf v}(i,{\bf a})}{i\in [k]\quad ,\quad {\bf
a}\in \F^{k-1}}
$$
As usual, to claim that this is infact a hitting set with the required
threshold, assume not. Then we have some circuit $C$ of size at most
$n^q$ accepting more than $\inparen{1 - \frac{2^{n^\epsilon}}{2^n}}$
fraction of inputs but none of $H_f$. Let us define two sets:
\begin{eqnarray*}
Z & = & \setdef{w\in \zo^n}{C(w) = 0}\\
L & = & \setdef{w\in \zo^n}{w = \inparen{p(x)}_{x\in \F} \text{ for
some low degree polynomial $p$}}
\end{eqnarray*}
Therefore, $S\subseteq Z\intersection L$. 

We now want to be able to do the following: given a vector ${\bf a }
= \inparen{a_1,\cdots, a_k}$, we want to compute $\tilde{f}({\bf
a})$ efficiently. We shall make good use of non-uniformity to get the
value of $\tilde{f}$ at a few points to be able to interpolate and
find $\tilde{f}$ at the required point. 

Elements of $Z \intersection L$ as a vector in $\F^{|\F|}$. Though it
has a huge number of coordinates, in order to distinguish two distinct
vectors in $Z \intersection L$, we just need a small number of
coordinates. This is summarized in this claim, which we won't prove
here; the proof isn't too difficult. 

\begin{claim}
There exists a subset $S$ of $\F$ of size less than $n^{\epsilon}$
such that the projection  $\pi_S:\F^{|\F|}\longrightarrow \F^{|S|}$ is
$1-1$ on $Z\intersection L$. 
\end{claim}
In fact, this is the place we use the fact that $C$ accepts a large
fraction of inputs. 

Now we shall say what advice we would be looking for, and how we can
then non-deterministically compute $\tilde{f}$ at a given point. We
would require the following things as advice:
\begin{enumerate}
\item The circuit $C$.
\item The set $S\subseteq \F$. 
\item $\tilde{f}$ on $S^k$, that is the values of $\tilde{f}$ on
vectors each of whose coordinates are from $S$. 
\end{enumerate}
Firstly, how big is the advice? The circuit $C$ is of size $n^q$, the
subset is of size $n^\epsilon$ and the values of $f$ at $S^k$ which is
$n^{\epsilon k}$ bits. Therefore, overall, for sufficiently large $m$,
the advice is $2^{cm\inparen{\epsilon + \frac{q}{m}}}$. Now all that
is left to do is to compute $\tilde{f}$ on ${\bf a}$ with the given
advice and we would have a contradiction to the hardness of $f$.\\

Given ${\bf a} = (a_1,\cdots, a_k)$, we want to compute
$\tilde{f}({\bf a})$. For each ${\bf u} \in \F^{k-1}$, do the
following: 
\begin{enumerate}
\item Guess ${\bf v} = \inparen{\tilde{f}(i,{\bf u})}_{i\in \F}$.
\item Check if ${\bf v}\in Z$ by checking if $C({\bf v}) = 0$. 
\item Check if ${\bf v}\in L$ by checking if it is a low degree
polynomial evaluated at a lot of points by just solving a bunch of
linear equations. 
\item After the above tests, we are sure that ${\bf v}\in
Z\intersection L$. Now use the above claim. Check if ${\bf v}_s
= \tilde{f}(s,{\bf u})$ for each $s\in S$ by looking up the table
provided as advice. If the values match for each $s\in S$, there is a
unique vector in $Z\intersection L$ that matches at that is indeed
$\inparen{\tilde{f}(i,{\bf u})}_{i\in \F}$. 
\item Add the value of ${\bf v}_{a_1} = \tilde{f}(a_1,{\bf u})$ to the table. 
\end{enumerate}

After we've got $\tilde{f}(a_1,{\bf u})$ for each ${\bf u}\in
S^{k-1}$, we proceed to get $\tilde{f}(a_1,a_2,{\bf u})$ for each
${\bf u}\in S^{k-2}$ in exactly the same way as outlined. Thus, we can
now express this as an SV non-deterministic circuit computing
$\tilde{f}$, and therefore $f$ of size at most $2^{cm\inparen{\epsilon
+ \frac{q}{k}}}$ for a sufficiently large $m$, contradicting the
hardness of $f$. 

Therefore, $H_f$ indeed has to be a hitting set generator with the
claimed parameters. 
\end{proof}

And that completes the proof of the main theorem as well. 

\subsection*{Summary:}

\begin{enumerate}
\item $\AM$ can, without loss of generality, be assumed to have
perfect completeness. Therefore, hitting sets with threshold $1/2$
suffice for derandomization.
\item Since explicit dispersers, the Disperser Lemma tells us that if
we have a HSG with threshold $1 - \frac{2^{n^\epsilon}}{2^n}$, that
can be pushed to give a HSG with threshold $1/2$. 
\item Given a hard function, we can use its evaluations at lines in
each dimension to argue that it is indeed a HSG with threshold $1
- \frac{2^{n^\epsilon}}{2^n}$. 
\end{enumerate}



\end{document}