\documentclass[11pt]{article}

\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{hyperref}

\newcommand{\handout}[5]{
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 5.78in { {\bf Lectures on Expanders} \hfill Course Instructor: #2 }
       \vspace{4mm}
       \hbox to 5.78in { {\Large \hfill #5  \hfill} }
       \vspace{2mm}
       \hbox to 5.78in { {\em #3 \hfill #4} }
      }
   }
   \end{center}
   \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{Lecturer: #3}{Scribe:
    #4}{Lecture#1}}

\newtheorem{theorem}{Theorem}
\newtheorem{theorem*}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}

%my custom commands
\newcommand{\norm}[1]{\left\Vert #1 \right\Vert}
\newcommand{\ltwo}[1]{\left\Vert #1 \right\Vert_2}
\newcommand{\lone}[1]{\left| #1 \right|_1}
\newcommand{\linf}[1]{\left| #1 \right|_{\infty}}
\newcommand{\innerp}[1]{\langle #1 \rangle}
\newcommand{\blah}{x\perp u,\norm{x}=1}
\newtheorem{subclaim}[theorem]{Subclaim}
\newcommand{\z}{\textcircled{z}}
\newcommand{\parn}[1]{\left( #1 \right)}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\f}{\mathbb{F}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\parl}{\parallel}
\newcommand{\md}[1]{\left|#1\right|}
\newcommand{\ldju[2]}{\bigcup_{#1}^{#2}\hspace{-9mm\cdot}\hspace{7mm}}

\begin{document}

\lecture{ $1$}{V. Arvind}{V. Arvind}{Ramprasad Saptharishi}


\section{Introduction}

\subsection{Motivation}

We would like to build a family of graphs that are ``sparse'' but
``highly'' connected. Some conditions that we would want our graphs
have are
\begin{enumerate}
\item The graph should be computable in time polynomial in the number
  of vertices
\item The graph should be edge-checkable in time poly logarithmic in
  the number of vertices. 
\item In the context of $d-$regular graphs, $A(x,i) = y$ if $y$ is the
  $i^{th}$ neighbour of $x$, and this $A$ should be polynomial time in
  its input length. 
\end{enumerate}

\subsection{Graph Parameters}

{\bf Sparseness:}

As for the graphs being sparse, the graphs we are looking for
shall be $d$ regular, for ``small'' $d$, and thus property $3$ would
be applicable. 

\bigskip

\noindent
{\bf Connectivity:}

A possible connectivity measure is the measure how much the graph
``expands''.

\begin{definition}\label{vertex_exp_defn}
A graph $G_n$ is said be a $(k,\alpha)$ vertex expander if for
all subsets $S$ of vertices such that $|S|\leq k$, the neighbourhood
of $S$, denotes by $\Gamma(S) \geq \alpha|S|$. 
\end{definition}

This is a natural notion of connectivity or expansion that we would
want ($\alpha$ ``large'' $implies$ ``expands well''), but
unfortunately, checking if a graph is a $(k,\alpha)$ is $coNP$
complete! Hence we need a different notion of expansion.

\section{Spectral Expansion}

\subsection{Associated Eigenvalues}

Let $G(V,E)$ be a $d$-regular multigraph, where there could be more
than $1$ edge between vertices. This could be thought of as a graph
with non-negative integral weights, where the weight of edge $ij$
denotes the number of edges between $i,j$.

Let $A$ be the {\em normalised adjacency matrix} of $G$
$$
A_{ij} = \frac{\text{number of edges between }i,j}{d}
$$

$A$ is a real, symmetric, doubly stochastic matrix\footnote{rows and
  columns entries are non-negative and add up to $1$}. And by the spectral
theorem, the eigenvalues of this matrix are real, and there exists an
eigenbasis. Let the eigenvalues be $\lambda_1, \lambda_2, \cdots,
\lambda_n$ such that $|\lambda_1|\geq |\lambda_2| \geq \cdots \geq
|\lambda_n|$

Suppose $\lambda$ is any eigenvalue of $A$ and $v$ an associated
eigenvector.

Let $|v_i| = \max_{1\leq j\leq n}|v_j|$

\begin{eqnarray*}
|\sum_{j=1}^n A_{ij}v_j| & =    & |\lambda||v_i|\\
                        & \leq & \sum_{j=1}^n |A_{ij}||v_j| \\
                        & \leq & |v_i|\sum_{j=1}^n |A_{ij}| \\
                        & =    & |v_i|
\end{eqnarray*}

Hence $|\lambda| \leq 1$

And since $A$ is a stochastic matrix, clearly $(1,1,\cdots, 1)$ is an
eigenvector whose eigenvalue is $1$. Speaking in terms of probability
distributions, it makes more sense to say that the uniform
distribution $u=\left(\frac{1}{n},\frac{1}{n},\cdots,
  \frac{1}{n}\right)$ is an eigenvector with eigenvalue $1$. 

Thus $\lambda_1 = 1$.

\subsection{Other Eigenvalues}

$\lambda_1 = 1$ for all graphs, we have to inspect the other
eigenvalues to see if they tell us anything about the graph's
expansion properties. Firstly, we need to see if any other
$|\lambda_i| = 1$. 

\noindent
First let's examine if any $\lambda_i = 1$.

\begin{lemma}The dimension of the eigenspace of $1$ $=$ number of
  connected components of $G$
\end{lemma}
\begin{proof}
Let $x\perp u$ and $Ax = x$. Let $x_i = \max x_j$, $X = \{k|x_k =
x_i\}$. 
$$
\sum_{j=1}^{n}A_{ij}x_j = x_i = \sum_{j,A_{ij}\neq 0} A_{ij}x_j
$$
which is a convex combination of $x_j$'s. Thus $A_{ij}\neq 0
\implies x_i = x_j$, which implies no edges go out of the set
$X$. Thus $X$ is a component of $G$. 

And if there are $k$ connected components, dimension of eigenspace of
$1$ is atleast $k$ (uniform distribution over that component is an
eigenvector). And since every connected component has only $u$ as its
eigenvector, the dimension of the eigenspace of $1$ is exactly $k$.
\end{proof}

Now for the case when $\lambda_i = -1$
\begin{lemma}
For a connected $d-$regular graph $G$, 
$$
G \text{ is bipartite } \iff  -1 \text{ is an eigenvalue}
$$
\end{lemma}

\begin{proof}
  Look at the graph $G^2$, whose edge relation correspond to paths of
  length $2$ in $G$. Note that the adjacency matrix of this graph has
  to be $A^2$ and hence the eigenvalues of $G^2$ has to be
  $\{\lambda_i^2\}_{i=1}^n$

  If $G$ is connected and bipartite, $G^2$ has $2$ component, and thus
  $G^2$ has an eigenvalue $1$ with multiplicity $2$. And since $G$ is
  connected, the eigenvalue $1$ of $G$ has multiplicity $1$, which
  implies $-1$ is an eigenvalue of $G$. 

  \medskip

  Conversely. let $-1$ be an eigenvalue of $G$ and $x$ the eigenvector
  chosen such that $\max x_j = \max |x_j| = x_i$(say).

  And repeating the argument in the earlier lemma,
  $$
  \sum_{j=1}^n A_{ij}x_j = -x_i = \sum_{j,A_{ij}\neq 0}A_{ij}x_j
  $$
  which is a convex combination of $x_j$. And hence, $A_{ij}\neq 0
  \implies x_j = -x_i$.
  
  Now let $X =\{ k | x_k = x_i\}$. Since $x_j = x_i \implies A_{ij} =
  0$, the induced subgraph on $X$ is empty. 

  Since the graph is connected, let $x_l$ be a vertex in $V \\ X$ that
  is connected to some $x_m$ in $X$. And since it is connected to some
  vertex in $X$, $A_{ml} \neq 0 \implies x_m = -x_i$
  
  $$
  \sum_j A_{lj}x_j = -x_l = x_i
  $$

  And this is possible only when $x_j = x_i$ wherever $A_{lj}\neq 0$,
  which means all the neighbours of $x_m$ are in $X$ - the graph is
  bipartite.
  
\end{proof}

Hence, if $G$ is connected, and not bipartite, $|\lambda_2|<1$. This
$|\lambda_2|$ is called the spectral expansion of $G$.

\begin{definition}
  For $G$, a connected $d-$regular non-bipartite graph, the spectral
  expansion of $G$ is $|\lambda_2| = \lambda_2(G)$
\end{definition}

We shall soon see that $1 - \lambda_2(G)$ is large $\implies$ good
vertex expansion. 

\begin{theorem}
  $$
  \lambda_2(G) = \max_{x\perp u} \frac{\norm{Ax}_2}{\norm{x}_2} =
  \max_{x\perp u} \frac{|\langle Ax,x \rangle|}{|\langle x,x \rangle|}
  $$
\end{theorem}
\begin{proof}
  Let $u=v_1, v_2, \cdots, v_n$ be an eigenbasis. For any $x\perp
  u$,
  \begin{eqnarray*}
  x & = &\alpha_2 v_2 + \alpha_3 v_3 + \cdots \alpha_n v_n\\
  \langle Ax , Ax \rangle  & = &\sum_{i=2}^n \alpha_i^2 \lambda_i^2
  \leq \alpha_2^2 \norm{x}_2
  \end{eqnarray*}
  and the equality is attained when $x$ is the eigenvector of $\lambda_2$

  The proof of the other equality is exactly the same.

\end{proof}

\begin{fact}
$\linf{v} \leq \ltwo{v} \leq \lone{v} \leq \sqrt{n}\ltwo{v}$
\end{fact}

\section{Random Walks on Expanders}

\subsection{Mixing Time and Spectral Expansion}
Let $\pi$ be a probability distribution over the vertices. Since $A$
is a stochastic matrix, $A\pi$ is also a probabilistic
distribution\footnote{this is the probabilistic distribution over the
  vertices after $1$ step is taken according to $\pi$}. 

\begin{definition}
  $G$ has mixing time $t(n)$ if for all probability distributions
  $\pi$
  $$
  \linf{A^{t(n)}\pi - u} \leq \frac{1}{2n}
  $$
\end{definition}

\noindent

\begin{theorem}
``Good Expanders have small mixing time''
\end{theorem}
\begin{proof}
Let $\lambda_2(G) = \lambda$ and $\pi$ be any probability
distribution. 
$$
\pi = \alpha_1 u + \alpha_2 v_2 + \cdots \alpha_n v_n
$$

Note that $\innerp{\pi,u} = \frac{1}{n}$ and hence $\alpha_1 =
1$. Hence

\begin{eqnarray*}
A^l\pi - u &= &\alpha_2 \lambda_2^l v_2 + \cdots + \alpha_n
\lambda_n^l v_n\\
\therefore \ltwo{A^l \pi - u}^2 & = &\alpha_2^2 \lambda_2^{2l} + \cdots +
\alpha_n^2 \lambda_n^{2l}\\
& \leq & \lambda_2^{2l}\left(\alpha_2^2 + \cdots + \alpha_n^2\right)\\
& \leq & \lambda_2^{2l} \ltwo{\pi - u}^2
\end{eqnarray*}

And since $\ltwo{pi}^2 = \ltwo{u}^2 + \ltwo{u^{\perp}}^2$, we have
$\ltwo{pi}^2 \geq \ltwo{\pi - u}^2$. 

Hence we now have,
$$
\linf{A^l\pi - u} \leq \ltwo{A^l\pi - u} \leq \lambda_2^l \ltwo{\pi}
\leq \lambda_2^l \leq \frac{1}{2n}
$$

Hence $l = \log_{\frac{1}{\lambda_2}}2n$

Thus for small $\lambda_2$, mixing time is small.
\end{proof}

\section{Undirected Graph Connectivity is in $RL$}

$$
UGAP = \{(G,s,t)| \exists s-t \text{ path in }G\}
$$

\begin{definition}
$RL$ is the class of languages $L$ that are accepted by a polytime
randomized logspace turing machine with onesided error.
\end{definition}

Note that the polynomial running time requirement is critical, since
we have a stream of random bits, the machine could run for much
longer. Randomized logspace machines running for more than polynomial
time arguably have more computational power than $RL$ machines. 

\begin{theorem}\label{UGAP}
  $UGAP\in RL$
\end{theorem}

We need some bounds before we get into the proof.

\subsection{Bounds on $\lambda_2(G)$}

Let $G$ be any arbitrary connected, non-bipartite regular
graph. Assuming that there are self loops on all the nodes of $G$,
$G^2$ will now be a regular, non-bipartite connected graph with all
its eigenvalues non-negative. Let the normalized adjacency matrix of
$G^2$ be $A$ and let $E$ be the multiset of edges. 

\begin{eqnarray*}
\lambda_2(G^2) &= &\max_{\blah}\left|\innerp{Ax,x}\right|\\
               &= &\max_{\blah}\left|\sum_{i,j}A_{ij}x_ix_j\right|\\
               &= &\max_{\blah}\left|\sum_{(i,j)\in E} \frac{2}{d}x_ix_j\right|\\
               &= &\max_{\blah}\left|\frac{1}{d}\sum (x_i^2 + x_j^2) -
               \frac{1}{d}\sum (x_i - x_j)^2\right|\\
               &= &\max_{\blah}\left|\frac{1}{d} d\norm{x}^2 - \frac{1}{d}\sum
               (x_i - x_j)^2\right|\\
\therefore 1 - \lambda_2 &= &\min_{\blah}\left|\frac{1}{d}\sum_{(i,j)\in
                 E}(x_i - x_j)^2\right|
\end{eqnarray*}

Let $x$ be the optimal vector for the above equation. Since $x\perp
u$, let $0<x_a = max x_i, x_b = min x_i < 0$. Since $\norm{x}=1$,
either $x_a \geq\frac{1}{\sqrt{n}}$ or $x_b \leq \frac{-1}{\sqrt{n}}$.
Let $P$ be the shortest path from $a$ to $b$ in $G^2$.

$$
\therefore (x_a - x_b) = \sum_{(i,j)\in P}(x_i - x_j) \geq \frac{1}{\sqrt{n}}
$$

\begin{eqnarray*}
1-\lambda_2(G^2) & \geq & \sum_{(i,j)\in P} (x_i - x_j)^2\\
                 & \geq & \frac{1}{d|P|}\left(\sum_{(i,j)\in P}|x_i -
                   x_j|\right)^2\\
                 & \geq & \frac{1}{dn}|x_a - x_b|^2 \geq  \frac{1}{dn^2}
\end{eqnarray*}
\begin{eqnarray*}
\therefore \lambda_2(G^2) &\leq &1 - \frac{1}{dn^2}\\
\implies \lambda_2(G) & \leq & 1 - \frac{1}{2dn^2}
\end{eqnarray*}
where $d$ is the degree of $G^2$, the square of the degree of $G$. 

Thus, $\lambda_2(G) \leq 1 - \frac{1}{poly(n)}$.

\subsection{Proof of Theorem \ref{UGAP}}

Replace every node of degree $k$ by a $k$ cycle, and add self loops to
make it a regular graph, and add self loops on all the nodes. 

We know that $\lambda_2(G) \leq 1 - \frac{1}{n^4}$. Suppose $A$ is the
normalized adjacency matrix. Then,
$$
\linf{A^{n^5} \pi - u} \leq \lambda_2^{n^5}\leq \left(1 -
  \frac{1}{n^4}\right)^{n^5} \leq \frac{1}{2n}
$$
Looking at the $t$-th index, 
\begin{eqnarray*}
\left| (A^{n^5}\pi)_t - \frac{1}{n}\right| &\leq &\frac{1}{2n}\\
\implies (A^{n^5}\pi)_t \geq \frac{1}{2n}
\end{eqnarray*}

Which means, 
$$
\Pr[\text{on a random walk, you don't hit }t\text{ in }n^5\text{
  steps}] \leq 1 - \frac{1}{2n}
$$
This error can be pushed down to the desired limit in logspace. \qed

\newpage
\lecture{ $2$}{V. Arvind}{V. Arvind}{Ramprasad Saptharishi}
\section{Amplification of success in $RP$}


Let $L\in RP$, accepted by a randomized algorithm $A$ with one-sided
error bounded by $\frac{1}{2}$. We shall use an expander graph to
boost the error probability by using fewer random bits compared to the
majority vote which uses $mk$ random bits to push the error down to $2^{-k}$. 

Assume that for inputs of length $n$, the machine takes $m = n^{O(1)}$
random bits. Consider $G(V,E)$, a $(2^m, d, \lambda)$ expander,
explicitly given\footnote{given $x$ and $i$ outputs $y$ which is the
  $i$-th neighbour of $x$ and runs in time $poly(m)$}. 

For $x\in L$, define $B = \{r \in \Sigma^m | A(x,r)=0\}$. And by the
error bound of $A$, we know that $|B| \leq 2^{m-1}$

Our algorithm is going to be the following:
\begin{enumerate}
\item Pick a vertex $r_0$ at random
\item Take a random walk for $t$ steps starting at $r_0$. Let the
  visited nodes be $r_0,r_1, \cdots r_t$. 
\item Use these $r_i$'s as random strings to $A$ and output ``YES'' if
  and only if atleast one of them say ``YES''.
\end{enumerate}

Now the question boils down to asking ``What is the probability that
after $t$ steps, we are confined to $B$?''

\begin{theorem}\label{rwalk_bound}
If $G$ is a $(2^m,d,\lambda)$ expander, and $B\subseteq V$ such that
$|B| \leq \mu |V|$, then 
$$
\Pr[r_0,r_1,\cdots, r_t \in B] \leq \left(\mu + (1-\mu)\lambda^2\right)^{\frac{t}{2}}
$$
\end{theorem}

And with the theorem, if $\mu = \frac{1}{2}$, we have the probability to
be bounded by $\left(\frac{1+\lambda^2}{2}\right)^{\frac{t}{2}}$,
which is $2^{-ct}$ for a constant $c$.

Hence, in order to push the down to $2^{-k}$, you want $t$ to be
 $O(k)$. And for a random walk for $k$ steps, you only need $m +
O(k)\log d$ random bits!

Now, the proof of the theorem is all that's left to justify the
amplification.

\subsection{Proof of Theorem \ref{rwalk_bound}}

Let $N = 2^m$ and  $P$ be the projector on $B$, that is
$$\left[
\begin{tabular}{c|c}
$I_{BxB}$ & 0\\
\hline
0 & 0
\end{tabular}
\right]_{N\times N}
$$

Note that $\lone{Pu} = \Pr[r_0 \in B]$. Infact one can extend this to
higher powers by the following claim. 

\medskip

\noindent
\begin{claim}
$\lone{P(AP)^iu} = \Pr[r_0,r_1, \cdots, r_i \in B]$
\end{claim}
\begin{proof}
The proof is just simple induction. We just saw the base case when
$i=0$. Assume that for some $i$
$$
\lone{P(AP)^iu} = \Pr[r_0,r_1, \cdots, r_i \in B]
$$
Now $A(P(AP)^iu)_j = \Pr[\text{the first }i\text{ steps are confined
  in }B\text{ and the last step takes it to }j]$. And by just summing
over all $j$ in $B$, we have
$$
\lone{P(AP)^{i+1}u} = \Pr[r_0,r_1, \cdots, r_{i+1} \in B]
$$
which proves the inductive step.
\end{proof}

Now we would like to bound $\lone{P(AP)^tu}$ for the proof.

\begin{claim}\label{apx_bound}
Let $x$ be any vector in,
$$
\ltwo{APx} \leq \sqrt{\mu + (1-\mu)\lambda^2}\cdot \ltwo{x}
$$
\end{claim}

And once we have this, we can just take $x = u$ and we would have
$$
\lone{P(AP)^tu} \leq \lone{(AP)^tu} \leq \sqrt{N}\left(\mu +
  (1-\mu)\lambda^2\right)^{\frac{t}{2}}\sqrt{N} = \left(\mu +
  (1-\mu)\lambda^2\right)^{\frac{t}{2}}
$$
which proves  theorem \ref{rwalk_bound}. 

\begin{proof}
  Let $y = Px$, and $y = y^\parallel + y^\perp = \alpha u +
  y^{\perp}$; note that $\alpha = \sum y_i$

\begin{eqnarray*}
 \ltwo{Ay}^2 &  = & \ltwo{Ay^\parallel}^2 + \ltwo{Ay^\perp}^2\\
 & = & \ltwo{y^\parallel}^2 + \ltwo{Ay^\perp}^2\\
 & \leq & \ltwo{y^\parallel}^2 + \lambda^2\ltwo{y^\perp}^2\\
 & = & \ltwo{y^\parallel}^2 + \lambda^2\left(\ltwo{y}^2 -
 \ltwo{y^\parallel}^2\right)
\end{eqnarray*}

Now 
\begin{eqnarray*}
\frac{\alpha^2}{n} = \ltwo{y^\parallel}^2 & = & \frac{\left(\sum_{i\in
      B}y_i\right)^2}{n}\\
 & \leq& \frac{\left(\sum_{i\in B} y_i^2\right)|B|}{n}\\
 & =   & \ltwo{y} \mu
\end{eqnarray*}

Hence, 
$$
\ltwo{Ay}^2 \leq \left(\mu + \lambda^2(1 - \mu)\right)\ltwo{y}^2 \leq
\left(\mu + \lambda^2(1 - \mu)\right) \ltwo{x}^2
$$
and that completes the proof of the claim
\end{proof}

\bigskip

\noindent
... and also the proof of theorem \ref{rwalk_bound} \qed  

\section{Spectral Expander $\implies$ Vertex Expander}

Recall definition \ref{vertex_exp_defn}  of a $(k,\alpha)$ expander:

\noindent For all subsets of vertices $S$ such that $|S|\leq k$,
$\Gamma(S) \geq \alpha|S|$.

\medskip

Now we shall show that a ``good'' spectral expander is also a ``good''
vertex expander. 

\begin{theorem}\label{spec_vert}
If $G(V,E)$ is a $(n,d,\lambda)$ spectral expander, then for every
$\alpha >0$, $G$ is an $\left(\alpha n,\frac{1}{(1-\alpha)\lambda^2 +
    \alpha}\right)$ vertex expander. 
\end{theorem}

\begin{proof}
Let $S\subseteq V$ such that $|S|\leq \alpha n$. Suppose $\pi$ is any
distribution over the vertices, it can be written as $u + u^\perp$. 
$$
\innerp{\pi, \pi} = \frac{1}{n} + \ltwo{\pi -u}^2
$$

Also, 
\begin{eqnarray*}
\innerp{\pi, \pi}& = & \sum_{i\in supp(\pi)}\pi_i^2 \\
 & \geq &\frac{\left(\sum \pi\right)^2}{|supp(\pi)|}\ \ \ \ \ \ \ \text{ (Cauchy Schwarz)}\\
 & = & \frac{1}{|supp(\pi)|}
\end{eqnarray*}

Suppose $\pi$ was the uniform distribution on $S$, then note that
$\innerp{\pi, \pi} = \frac{1}{|S|}$. 

Hence, 
$$
\ltwo{\pi -u}^2 = \frac{1}{|S|} - \frac{1}{n}
$$

Since $supp(A\pi) = \Gamma(S)$,
\begin{eqnarray*}
\frac{1}{|\Gamma(S)|} &\leq &\innerp{A\pi, A\pi}  = \frac{1}{n} +
\ltwo{A\pi - u}^2\\
 &  \leq & \frac{1}{n} + \lambda^2 \ltwo{\pi - u}^2\\
 & = & \frac{1}{n} + \lambda^2\left(\frac{1}{|S|} -
   \frac{1}{n}\right)\\
\implies \frac{|S|}{|\Gamma(S)|} & \leq & \frac{|S|}{n} +
\lambda^2\left(1 - \frac{|S|}{n}\right)\\
& = & \frac{|S|}{n}\left(1 - \lambda^2\right) + \lambda^2\\
& \leq & \alpha\left(1 - \lambda^2\right) + \lambda^2
\end{eqnarray*}

Therefore, 
$$
\frac{|\Gamma(S)|}{|S|} \geq \frac{1}{\alpha\left(1 - \lambda^2\right)
  + \lambda^2} = \frac{1}{\lambda^2\left(1 - \alpha\right) + \alpha}
$$

\end{proof}

\subsection{Lower Bounds on $\lambda$}

Theorem \ref{spec_vert} tells much more than an implication. 

For any $d$ regular graph, the vertex expansion of this graph is
atmost $d$. 

\begin{eqnarray*}
\implies \frac{1}{\alpha + \left(1-\alpha\right)\lambda^2} & \leq & d\\
\implies \lambda^2\left(1 - \alpha\right) & \geq & \frac{1}{d} - \alpha
\end{eqnarray*}

Taking  $\alpha$ close to $0$, we see that $\lambda =
\Omega(\frac{1}{\sqrt{d}})$. 

\noindent
Infact there are better bounds known, Alon and Bopanna show that
$$\lambda \geq \frac{2\sqrt{d-1}}{d} - o(1)$$
Ramanujam graphs get very close to this optimal\footnote{they have
  $\lambda = \frac{2}{\sqrt{d-1}} - o(1)$}.

\section{Random Graphs as Expanders}

Instead of looking at general random graphs, we shall restrict
ourselves to bipartite graphs and show that a random bipartite graph
is a ``good'' {\em left expander}.

\begin{definition}
  A bipartite multigraph $G(L\cup R,E)$ is a $(d,k,\alpha)$
  left expander if every vertex on $L$ has degree $d$, and for all
  subsets $S$ of vertices in $L$ such that $|S| \leq k$, $|\Gamma(S)|
  \geq \alpha|S|$
\end{definition}

Random bipartite graphs are chosen in the following sense, for every
vertex $v\in L$ randomly pick $d$ vertices from $R$ with
repitition. For simplicity of notation, let us call the set of
possible multigraphs $\mathcal{G}_{n,d}$.

\begin{theorem}
For every $n$ and $d\leq n$, there exists an $\alpha > 0$ such that
random $G\in \mathcal{G}_{n,d}$ is a $(d,\alpha n, d-2)$ left
expander with probability greater than $\frac{1}{2}$
\end{theorem}

\begin{proof}

Let $S\subseteq L$, such that $|S|=k<\alpha n$, we shall estimate the
$\Pr_{G}[|\Gamma(S)|< (d-2)|S|]$.

For every vertex $v\in L$, we chose $d$ neighbours, which is $kd$
elements picked from $L$. Thus, we want to estimate the probability
that there are atleast $2k$ repititions. There are $\binom{kd}{2k}$
places where the collisions can occur and each collision with
probability $\frac{kd}{n}$. 

$$
\therefore Pr_{G}[|\Gamma(S)|<(d-2)|S|] \leq \binom{kd}{2k}\left(\frac{kd}{n}\right)^{2k}
$$

Summing over all $S$, 
\begin{eqnarray*}
\sum_{k=1}^{\alpha n} \binom{n}{k} \binom{kd}{2k}
\left(\frac{kd}{n}\right)^2k & \leq & \sum_{k=1}^{\alpha
  n}\left(\frac{ne}{k}\right)^k
\left(\frac{kde}{2k}\right)^{2k}\left(\frac{kd}{n}\right)^{2k}\\
& = & \sum_{k=1}^{\alpha n}\left(\frac{kd^2e^3}{4n}\right)^k \\
& \leq & \sum_{k=1}^{\alpha n}\left(\frac{\alpha d^2 e^3}{4}\right)^k
\end{eqnarray*}

And clearly for $\alpha<\frac{1}{d^2e^3}$ this probability can be
bounded by half. 
\end{proof}
\section{Explicit Constructions}

The earliest explicit constructions of expander graphs were given by
[Margulis,Gabber-Galil], [Lubotzky,Sarnak] but the contructions are
fairly complex, looks at certain subsets of matrix groups. 

[Reingold,Vadhan,Wigderson] used ``zig-zag products'' to construct
expanders, we shall be looking at them in the next lecture. Gramov had
used this zig-zag products earlier, though the novelty is attibuted to
[RVW]. 
Zig-zag products seem to mimic the semi-definite over groups. 

Alon et al gave another ``not-so-difficult'' construction for
expanders, infact he said something more.

\begin{theorem}[Alon/Roichman]
There exists a constant $c$ such that for every finite group $G$, a
random set of $c\log n$ elements define a ``good'' expander in the
Cayley graph on the vertices. 
\end{theorem}

\newpage 
\lecture{ $3$}{V. Arvind}{V. Arvind}{Ramprasad Saptharishi}
In this lecture we shall be discussing the paper ``'Entropy Waves',
the zig-zag produt and new constant degree expanders'' by Reingold,
Vadhan and Wigderson, which appeared in the Annals of Mathematics
$'02$. 

\section{The Rotation Map}

Let $G$ be an $N$ vertex $D$ regular graph. The rotation map is a map
$Rot_G:[N]\times [D] \rightarrow [N]\times [D]$, defined as follows.

If $i^{th}$ edge of vertex $v$ is $w$, as a $j^{th}$ neighbour, then
$$
Rot_G(v,i) = (w,j)
$$

Note that this map is also an involution. This map defines the graph,
and we would want this to be efficient ($poly(\log N,\log D)$
computable, in this lecture).

\section{Graph Products}
We shall now inspect various graphs products possible and the
parameters of the graph.

\subsection{Powering}

Let $G$ be a $(N,D,\lambda)$ expander, given by the rotation map
$Rot_G$. Then its $i^{th}$ power, $G^t$ is given by the following
rotation map:
$$
Rot_{G^t}(v_0,(k_1, k_2,\cdots, k_t)) = (v_t,(l_t, \cdots, l_1))
$$
{\em if and only if} there exists $v_1,\ldots, v_{t-1}$ such that
\begin{eqnarray*}
Rot_G(v_0,k_1) & = &(v_1, l_1)\\
Rot_G(v_1,k_2) & = &(v_2, l_2)\\
 &\vdots & \\
Rot_G(v_{t-1},k_t) &= &(v_t, l_t)
\end{eqnarray*}

\medskip

And easy to see that $Rot_{G^t}$ is efficiently computable, and infact
the adjacency matrix of $G^t$ is $A^t$. Hence, $G^t$ is a $(N,D^t,
\lambda^t)$ expander. 

\subsection{Tensoring}

$G_1$ is a $(N_1, D_1, \lambda_1)$ expander, and $G_2$ is a $(N_2,
D_2, \lambda_2)$ expander and let $Rot_{G_1}$ and $Rot_{G_2}$ be the
corresponding rotation maps. 

The rotation map of $G_1\otimes G_2$ is defined by moving parallel on
$G_1$ and $G_2$. 

$$
Rot_{G_1\otimes G_2} \parn{(v,w),(i,j)} = \parn{(v',w'),(i',j')} 
$$
{\em if and only if}
$Rot_{G_1}(v,i) = (v',i')$ and $Rot_{G_2}(w,j) = (w',j')$.

Now, it is easy to see that the normalized adjacency matrix of this
graph, $A_{G_1\otimes G_2} = A_{G_1} \otimes A_{G_2}$, the tensor
product of the corresponding matrices\footnote{each $i,j$-th entry of
  $A_1$ is replaced by the block $(A_1)_{i,j} \cdot A_2$}

The eigenbasis will also be the tensor products of the eigenbases of
the two matrices, and hence the eigenvalues will be the products of
the eigen values. And since $1$ is an eigen value for both $A_1$ and
$A_2$, the second largest eigenvalues is $\max(\lambda_1, \lambda_2)$.

\medskip

Thus, $G_1\otimes G_2$ is a $\parn{N_1N_2, D_1D_2, \max(\lambda_1,
  \lambda_2)}$ expander. 

\bigskip

Both the products blows up the degree of the final graph, which is not
desired. We want a family of graphs with constant degree and good
spectral gap\footnote{$1 - \lambda(G)$}. 

\section{The Zig-Zag Product}

Let $G_1$ be a $(N,D,\lambda_1)$ expander and $G_2$ be a
$(D,d,\lambda_2)$ expander, with rotation maps $Rot_{G_1}$ and
$Rot_{G_2}$

Define the the graph $G_1 \z G_2$ as follows: 

\begin{itemize}
{\item $V(G_1\z G_2) = [N]\times [D]$, replace every vertex in $G_1$
  by a cloud of vertices in $G_2$, since the degree of $G_1$ matches
  with vertex size of $G_2$, this can be done.}
{\item An edge in $G_1\z G_2$ is defined by a three step walk, $1$
  move in the $G_2$ cloud, take and edge of $G_1$ and move to another
  cloud, $1$ move in the new cloud. More formally,

  $$
  \parn{(v,k),(w,l)} \in E[\parn{G_1\z G_2}]
  $$
  if, there exists numbers $k',l'$ such that
  \begin{eqnarray*}
  (k,k')&\in& E(G_2)\\
  (l,l')&\in& E(G_2)\\
  Rot_{G_1}(v,k')& = &(w,l')
  \end{eqnarray*}
}
\end{itemize}

So $G_1\z G_2$ is a $\parn{ND,d^2,\lambda_3}$ expander. 

\begin{theorem}[Zig-Zag Theorem]\label{zigzagthm}
For $G_1$ and $G_2$ considered above, $G_1\z G_2$ is a $\parn{ND, d^2,
  \lambda_3}$ expander where, 
\begin{enumerate}
\item $\lambda_3 \leq \lambda_1+\lambda_2 + \lambda_2^2$
\item If $\lambda_1 <1$ and $\lambda < 1$, then $\lambda_3 < 1$
\end{enumerate}
\end{theorem}

We shall prove this later.

\subsection{Intuition Behind this}

To be filled up soon

\section{A Constant Degree Expander Family}

Our base graph $H$ would be a $\parn{D^8, D, \lambda}$ expander for a
constant $D$, which we shall explicitly construct later.

The family $\{G_t\}$ is defined as follows:
\begin{eqnarray*}
G_1 & = & H^2\\
G_2 & = & H\otimes H\\
\forall t>2,\ \ \  G_t & = & \parn{G_{\ceil{\frac{t-1}{2}}} \otimes
  G_{\floor{\frac{t-1}{2}}}}^2 \z H
\end{eqnarray*}

\begin{claim}
$G_t$ is a $\parn{D^{8t},D,\lambda_t}$ expander, where $\lambda_t =
\lambda + O(\lambda^2)$, and whose rotation map is computable in time
polynomial in $\parn{t,\log N,\log D}$ with $poly(t)$ queries to the
rotation maps in the recursion. 
\end{claim}

\begin{proof}
The ambiguity is only in $\lambda$ of $G_2$, it's clear that the
vertex size of $G^t$ is $D^{8t}$ and that the parameters match for
zig-zag. 
\medskip

$\lambda_1 = \lambda^2 \leq \lambda + c\lambda^2$, and $\lambda_2 =
\lambda \leq \lambda + c\lambda^2$, we shall now proceed by
induction. 

Let $\mu_t = \max_{i} \lambda_i = \max(\lambda_t,\mu_{t-1})$. We know
that $\mu_1$ and $\mu_2$ are upper bounded by $\lambda +
c\lambda^2$. Assume by induction that $\mu_{t-1} \leq \lambda +
c\lambda^2$. 

Now, $G_t = K \z H$, where $K$ is the chunk in the definition. Note
that $\lambda_k \leq \mu_{t-1}^2 $.
Hence by the Zig-Zag theorem,  we know that
\begin{eqnarray*}
\lambda_t & \leq & \mu_{t-1}^2 + \lambda + \lambda^2\\
 & \leq & (\lambda+c\lambda^2)^2 + \lambda + \lambda^2
\end{eqnarray*}

We want this to be less than $\lambda + c\lambda^2$ for some $c$. It's
easy to see that if $\lambda \leq \frac{1}{5}$, then $c=5$ is good
enough. 

Thus we have a uniform family of constant degree expanders, with good
spectral gap. 
\end{proof}

Also note that in the earlier lecture we showd that $\lambda \leq
\frac{2}{\sqrt{D}}$, and hence
$$
\lambda_t \leq \lambda + c\lambda^2 \leq \frac{2}{\sqrt{D}} +
\frac{4c}{D} \leq \frac{c}{\sqrt{D}}
$$
And thus $\lambda_t = O\parn{\frac{1}{(deg(G))^{1/4}}}$.

\subsection{An explicit construction for $H$}

Let $q = p^t$, some prime power, and $\f_q$ be the associated
field. Our graph $AP_q$ is going to have the vertex set $V = \f_q \times
\f_q$. 

As for the edge set of the graph, for every vertex $(a,b)\in \f_q
\times \f_q$, define the set of vertices adjacent to $(a,b)$ as
$L_{a,b}$ where
$$
L_{a,b} = \{ (x,y) | y = ax - b\}
$$

And since $|L_{a,b}| = q$, we have a $q$ regular graph. 

\begin{claim}
$AP_q$ is a $\parn{q^2, q, \frac{1}{\sqrt{q}}}$ expander. 
\end{claim}
\begin{proof}
Let $M$ eb the normalized adjacency matrix of $AP_q$. $M^2$ is a $q^2
\times q^2$ matrix. And note that

\begin{eqnarray}
M^2_{(a,b),(c,d)} = \frac{1}{q^2}\left| L_{a,b} \bigcap L_{c,d}\right| \label{eqn1}
\end{eqnarray}



If $(x,y)$ is a common point, then 
$$
\left(\begin{array}{cc}
a & -1 \\
c & -1
\end{array}\right) = \parn{\begin{array}{c} x \\ y\end{array}}
$$

When $a\neq c$, the matrix is of rank $1$ and hence by equation
\ref{eqn1} $$M^2_{(a,b),(c,d)} = \frac{1}{q^2}$$. 

\noindent
Suppose $a=c$, if $b\neq d$, there are no solutions and hence
$M^2_{(a,b),(c,d)} = 0$. 

\noindent If $a=c$ and $b=d$, there are $q$ points in
common and hence $M^2_{(a,b),(c,d)} = \frac{1}{q}$

Thus the $M' = q^2M^2$ has the following form
$$
M' = \parn{\begin{array}{cccc}
           qI_q & J_q & \cdots & J_q\\
           J_q  & qI_q& \cdots & J_q\\
          \vdots&     & \ddots & \\
           J_q  & \cdots & J_q & q_Iq 
       \end{array}} 
$$
or in other words, 
$$
M' = \parn{I_q\otimes qI_q + (J_q - I_q)\otimes J_q}
$$
where $J_q$ is the $q\times q$ matrix with every entry being a $1$.
 
The only eigenvalue of $I_q\otimes qI_q$ is $q$. 

As for the other sum, $J_q - I_q$ has eigenvalue $q-1$ with
multiplicity $1$ and $-1$ with multiplicity $q-1$. 

And $J_q$ has eigenvalue $q$ with multiplicity $1$ and $-1$ with
multiplicity $q-1$. Hence $(J_q - I_q)\otimes J_q$ has eigen value
$q(q-1)$ with multiplicity $1$, $0$ with multiplicity $q(q-1)$ and
$-q$ with multiplicity $q-1$. 

Hence $M'$ has eigenvalue $q^2$ with multiplicity $1$, $q$ with
multiplicity $q(q-1)$ and $0$ with multiplicity $q-1$. 

Hence, clearly, the second largest eigenvalue of $M'$ is atmost $q$,
and hence the second largest eigenvalue of $M$ is atmost $\frac{1}{\sqrt{q}}$
\end{proof}

Now let $AP_q^1 = AP_q \otimes AP_q$, which gives a $\parn{q^4, q^2,
  \frac{1}{\sqrt{q}}}$ expander.

Define 
$$
AP_q^i = AP_q^{i-1}\z AP_q
$$

And then we have the following claim, which is easy to prove.
\begin{claim}
$AP_q^i$ is a $\parn{q^{2(i+1)},q^2, \frac{2i}{\sqrt{q}}}$ expander.
\end{claim}

And with this, if we were to choose $i=7$, and $q>70^2$, we have a
$H=AP_{5000}^7$ as our $(D^8,D,\frac{1}{5})$ expander. 

\newpage 
\lecture{ $4$}{V. Arvind}{V. Arvind}{Ramprasad Saptharishi}
\section{Overview}

We saw that the zig-zag product gave us a uniform family of
expanders. In the next two lectures we shall prove Reingold's
Theorem. 

First let us look at the rotation map of the zig-zag product as an
algorithm. 
\medskip

\noindent
$
Rot_{G_1 \z G_2}:
$

Input: $\parn{(v,k),(i,j)}$
\begin{eqnarray*}
(k',i')&:= &Rot_{G_2}(k,i)\\
(w,l')& := & Rot_{G_1}(v,k')\\
(l,j')& := & Rot_{G_2}(l',j)
\end{eqnarray*}
\indent
Output: $\parn{(w,l),(j',i')}$
\medskip

\noindent
Notice that this is a logspace algorithm and requires just $O(1)$
extra space apart from storing the $4$ vertices in consideration; this
would crucial in Reingold's proof.

\section{Proof of the Zig-Zag Theorem (\ref{zigzagthm})}
We shall prove only one of the results stated in the previous
lecture.

We have to study the second largest eigenvalue of $G_1\z G_2 = G$, for
which we need to look at the normalized adjacency matrix of $G$. Let
the normalised adjacency matrix of $G_2$ be $A$, and let $P$ be a
permutation matrix defining the rotation map of $G_1$.

Every edge of $G$ consists of a three step walk, the first one being a
walk in one of the $v$ clouds that are expanded to a $G_2$. Thus that
step can be represented by the matrix $B = I_N \otimes A$.

Thus the transition matrix of $G$ is simply $Z = BPB$.

In order to analyse the spectral gap of $Z$, let $f\in \R^{ND},
\ltwo{f} = 1,f\perp 1_{ND}$. We want to show that 
$$
\md{\innerp{f,Zf}} \leq \lambda_1 + \lambda_2 + \lambda_2^2
$$
Let $f = f^\parl + f^\perp$, where $f^\parl$ is a vector such that
$$
f^\parl_{(v,i)} = \frac{1}{D}\sum_{j=1}^D f(v,j) = \alpha_v
$$
which makes it locally uniform in each cloud $G_2$, hence $Bf^\parl =
f^\parl$. And, it also ensures that
$$
\sum_{v,i}f^\parl_{(v,i)} = \sum_{v,j} f_{(v,i)} = 0
$$
and hence $f^\parl$ and $f^\perp$ are orthogonal to $1_{ND}$.

Note that since $BPB$ is symmetric, $\innerp{f^\perp,BPBf^\parl} =
\innerp{f^\parl,BPBf^\perp}$. We then have, 
\begin{eqnarray*}
\md{\innerp{f,BPBf}} & = &\md{\innerp{f^\parl,BPBf^\parl} +
  2\innerp{f^\parl,BPBf^\perp} + \innerp{f^\perp, BPBf^\perp}}\\
 & \leq & \md{\innerp{f^\parl,BPBf^\parl}} +
  2\md{\innerp{f^\parl,BPBf^\perp}} + \md{\innerp{f^\perp,
      BPBf^\perp}}\\
 & = & (1) + (2) + (3)
\end{eqnarray*}
where $(1) = \md{\innerp{f^\parl,BPBf^\perp}}, (2) =
2\md{\innerp{f^\parl,BPBf^\perp}},(3) = \md{\innerp{f^\perp, BPBf^\perp}} $

\subsection*{Bounding $(1)$}

\begin{eqnarray*}
(1) & = & \md{\innerp{f^\parl, BPBf^\parl}}\\
    & = & \md{\innerp{Bf^\parl, PBf^\parl}}\\
    & = & \md{\innerp{f^\parl, Pf^\parl}}
\end{eqnarray*}

Now 
\begin{eqnarray*}
\innerp{f^\parl,Pf^\parl} & = &
\sum_{(v,i)}\sum_{(w,j)}P_{(v,i),(w,j)}f^\parl_{(v,i)}f^\perp_{(w,j)}\\
 & = & \sum_{(v,i)}\sum_{(w,j)}P_{(v,i),(w,j)}\alpha_v \alpha_w\\
 & = & \sum_{(v,w)\in E} D\alpha_v \alpha_w
\end{eqnarray*}

And if we were to choose $g =
\parn{\sqrt{D}\alpha_{v_1},\sqrt{D}\alpha_2,\cdots,\sqrt{D}
  \alpha_{v_N}}$, the above sum is just $\innerp{g,Ag}$. Now $g \perp
1_N$ and $\ltwo{g} = \ltwo{f^\parl}$. Hence

$$
(1) = \md{\innerp{g,Ag}} \leq \lambda_1 \ltwo{g} = \lambda_1
\ltwo{f^\parl} \leq \lambda_1
$$

\subsection*{Bounding $(2)$}

Since $\sum_i f^\parl_{(v,i)} = \sum_i f_{(v,i)}$ for all $v$, it
forces that $\sum_i f^\perp_{(v,i)} = 0$, or $f^\perp_v \perp 1_D$,
the projection of $f^\perp$ on $v$. 

And hence
\begin{eqnarray*}
\ltwo{Af^\perp_v} &\leq& \lambda_2 \ltwo{f^\perp_v}\\
\implies \ltwo{Bf^\perp} &\leq& \lambda_2 \ltwo{f^\perp}\\
\end{eqnarray*}

Thus,
\begin{eqnarray*}
(2) & = & 2\md{\innerp{f^\parl,BPBf^\perp}}\\
    & = & 2\md{\innerp{Bf^\parl,PBf^\perp}}\\
    & = & 2\md{\innerp{f^\parl,PBf^\perp}}\\
    & \leq & 2\ltwo{f^\parl} \ltwo{PBf^\perp}\\
    & = & 2\ltwo{f^\parl} \ltwo{Bf^\perp}\\
    & \leq & 2\lambda_2 \ltwo{f^\parl} \ltwo{f^\perp}
\end{eqnarray*}

\footnote{we used some other method in class first, but this seemed to
  be an easier proof}By the AM-GM inequality,
$2\ltwo{f^\parl}\ltwo{f^\perp} \leq \ltwo{f^\parl}^2 +
\ltwo{f^\perp}^2 = \ltwo{f}^2$

And hence, 
$$
(2) \leq \lambda_2 \ltwo{f} \leq \lambda_2
$$

\subsection*{Bounding $(3)$}

\begin{eqnarray*}
(3) & = & \md{\innerp{f^\perp,BPBf^\perp}}\\
    & = & \md{\innerp{Bf^\perp, PBf^\perp}}\\
    & \leq & \ltwo{Bf^\perp}\cdot\ltwo{PBf^\perp}\\
    & = & \ltwo{Bf^\perp}^2\\
    & \leq & \lambda_2^2 \ltwo{f}^2\\
    & \leq & \lambda_2^2
\end{eqnarray*}

Thus, $\lambda(G_1\z G_2) \leq \lambda_1 + \lambda_2 + \lambda_2^2$ \qed

\section{Towards Reingold's Theorem}

\begin{theorem}[Reingold]\label{reingold}
$UGAP \in L$
\end{theorem}

Instead of looking at $s-t$ connectivity over general graphs, we shall
see that if the connected component containing $s$ was a
$\lambda$-spectral expander for some constant $\lambda<1$, then we can
check connectivity in $L$

First, we shall expand every vertex to a cycle, so that we get a $D$
regular graph. 

Let $A$ be the adjacency matrix of $G$. We know that the mixing time
of $l = O(\log_{\frac{1}{\lambda}}N) = O(\log N)$. Thus for any
distribution over the connected component of $s$, 
$$
\linf{A^le_s - u_s} \leq \frac{1}{2N}
$$
and in particular, $(A^le_s)_t \geq {1}{2N}$ if it is inside the
connected component. Hence, if there exists a path from $s$ to $t$,
the path is of length atmost $O(\log N)$. 

But how does one enumerate all paths of length $O(\log N)$? The naive
method of remembering all vertices in the path would cost you
$O(\log^2 N)$ space. But since the graph is $D$ regular for some
constant $D$, it suffices to remember the out-edge number! Thus, the
space you need to try out all paths of length $O(\log N)$ would be
$O(\log D, \log N) = O(\log N)$, and this gives us the logspace
algorithm. 

\bigskip

Reingold's theorem basically forces every graph $G$ to be transformed
of one of the above category. 

For any $G = (N,D,\_)$ graph,
\begin{enumerate}
\item Pick $H$, a small $\parn{D^{16},D,\frac{1}{2}}$ expander. 
\item $G_0 = G, G_i = \parn{G_{i-1}\z H}^8$
\item Thus, $G_i$ is a $\parn{ND^{16i},D^{16},\_}$ graph. 
\end{enumerate}

Looking at the connected component containing $s$, turns out that
$$
\lambda(G_i) \leq \max[\lambda(G_{i-1})^2 ,\frac{1}{2}]
$$
And now, choosing $i=l=5\log N$ or so, we have 
$$
\lambda \leq \parn{1 - \frac{1}{N^4}}^{2^l} \leq \frac{1}{2}
$$
and this reduces to the earlier case which is solvable in logspace. 

The heart of the proof is to show that the rotation maps of $G_i$'s
can be computed in logspace.\footnote{though it seems like we need to
  make $O(\log N)$ recursive calls, the amortized cost of computing
  the rotation map is still $O(\log N)$}

\newpage
 \lecture{ $5$}{V. Arvind}{V. Arvind}{Ramprasad Saptharishi}
\section{Overview}

We are on our way to showing that $UGAP$ or undirected graph
connectivity can be computed in logspace. Last class we saw that if
the connected component containing $s$ was an expander with some
constant positive spectral gap, then we can check connectivity it in
logspace.

We shall now see how we can ``expanderize'' graphs in logspace, and
thus solve $UGAP$ in logspace. 

\section{Reingold's Algorithm}

\begin{enumerate}
\item Choose a graph $H$ that's a $\parn{D^{16},D,\frac{1}{2}}$
  expander for some constant $D$. 
\item Convert $G$ into a $D^{16}$ regular graph $G'$ with $N'=N^2$
  many vertices. We shall elaborate on how to do this shortly. 
\item Let $G_0 = G'$, and for all $i\geq 1$, 
$$
G_i = \parn{G_{i-1}\z H}^8 = T_i(G',H)
$$
Thus, $G_i$ would be a $\parn{N^2D^{16i},D^{16},\_}$ expander. 

\end{enumerate}

Now we have the following claims

\begin{claim}\label{rein_resp_conn} 
If $S$ is a connected component of $G$, 
$$
T_i(G'|_S,H) = T_i(G',H)|_{S\times [D^{16}]^i}
$$
\end{claim}

This basically tells us that the products respect connected
components, and hence connectivity.

\begin{claim}\label{rein_lambda_bound}
  For all $i\geq 1$, if $\lambda_i$ is the second largest eigenvalue of
  the connected component of $G_i$ containing $s$, then 
$$
\lambda_i \leq \max\parn{\lambda_{i-1}^2,\frac{1}{2}}
$$
\end{claim}

With this claim, if we choose $i=O(\log N)=l$, we have 
$$
\lambda_i = \parn{1 - \frac{1}{poly(N)}}^{2^i} < \frac{1}{2}
$$
And then our problem would reduce to the case we discussed last
lecture. 

\medskip

\noindent
But we need one more crucial claim, that allow us to take the
products.

\begin{claim}\label{rein_rotmap}
$Rot_{G_l}$ can be computed in logspace from $Rot_{G'}$ and $Rot_H$
\end{claim}

\medskip

\noindent 
So with the three claims, the algorithm is complete and we are done by
just applying the algorithm discussed last class for constant spectral
gap!

\subsection{Converting $G$ to a $D^{16}$-regular graph $G'$}

Let the vertex set of $G'$ be $[N]\times [N]$. 

$$
Rot_{G'}: \parn{[N]\times [N]}\times [D^{16}] \rightarrow
\parn{[N]\times [N]}\times [D^{16}]
$$
is defined as follows
\begin{itemize}
{\item For all $(v,w)\in [N]\times [N]$,
$$
((v,w),1)\mapsto ((v,w'),2)
$$
where $w' = w+1$ if $w<N$ and $w'=1$ when $w=N$,
}
{\item For all $(v,w)\in [N]\times [N]$,
$$
((v,w),2)\mapsto ((v,w'),1)
$$
where $w' = w-1$ if $w>1$ and $w'=N$ when $w=1$,
}
{\item 
  If $(v,w)\in E$, then
  $$
  ((v,w),3)\mapsto ((w,v),3)
  $$
  else
  $$
  ((v,w),3)\mapsto ((v,w),3)
  $$
}
{\item For all $3<i\leq D^{16}$
  $$
  ((v,w),i) \mapsto ((v,w),i)
  $$
}
\end{itemize}

This clearly gives us a $D^{16}$ regular graph which doesn't alter
connected components of the $G$. 

\subsection{Proof of Claim \ref{rein_resp_conn}}

Since this is a property that we would expect graph products to
preserve, let us examine all graph products.

Suppose $G_1$ and $G_2$ are two disjoint components of a graph, and
for any $G_3$ chosen appropriately for the products to be well
defined,
\begin{itemize}
{\item $\parn{G_1 \sqcup {G_2}}^t = {G_1^t}\sqcup {G_2^t}$

This is clear since powering cannot add cross edges between components
}
{\item $\parn{{G_1}\sqcup{G_2}}\otimes G_3= \parn{{G_1\otimes
      G_3}}\sqcup {\parn{G_2 \otimes G_3}}$

This again is clear since parallel edges can't create crosses between
components. 
}
{\item $\parn{{G_1}\sqcup{G_2}}\z G_3= {\parn{G_1\z G_3}}\sqcup{\parn{G_2 \z G_3}}$
The step on the clouds doesn't allow you to move across vertices of
the bigger graph. And one can move across vertices of the bigger
graphs only using the edges of the bigger graph. Hence this is also
clear. 
}
\end{itemize}

In the zig-zag product case, through the eigenvalues of the product
graph, we know that the resulting graph is connected if the components
of the product are connected. 

And with this, the proof of the claim is just a simple inductive
argument on $i$ where the products preserve the components and the
powering gives the extra $[D^{16}]$ to the LHS. \qed

\subsection{Proof of Claim \ref{rein_lambda_bound}}

For this we need a stronger bound on the eigenvalue of the zig-zag
product, the proof of this shall not be done here but can be found in
[ReingoldVadhanWigderson] where they discuss the zig-zag product. 

\begin{theorem}
If $\lambda_1,\lambda_2,\lambda_3$ are the spectral expansions of
$G_1, G_2$ and $G_1\z G_2$ respectively, then
$$
\lambda_3 \leq 1 - \frac{1}{2}(1-\lambda_2^2)(1 - \lambda_1)
$$
\end{theorem}

\noindent
Now for our case, $\lambda_2 \leq \frac{1}{2}$ and hence
$$
\lambda_3 \leq 1 - \frac{1}{2}\parn{1 - \frac{1}{4}}(1 - \lambda_1) \leq 1
- \frac{3}{8}(1 - \lambda_i)
$$

Now $G_i = \parn{G_{i-1}\z H}^8$ and hence 
$$
\lambda_i \leq \parn{1 - \frac{3}{8}(1 - \lambda_{i-1})}^8 \leq \parn{1 -
  \frac{1}{3}(1 - \lambda_{i-1})}^8
$$

If $\lambda_{i-1} \geq \frac{1}{2}$, $\lambda_i \leq \parn{\frac{5}{6}}^8
< \frac{1}{2}$.

Otherwise if $\lambda_{i-1} < \frac{1}{2}$, with some little bit of
calculus one can show that 
$$
\parn{1 - \frac{1}{3}(1 - \lambda_{i-1})}^4 \leq \lambda_{i-1}
$$
\indent
and we are done. \qed

\subsection{Proof of Claim \ref{rein_rotmap}}

Now we shall give a logspace algorithm to compute $Rot_l$ given
$Rot_{G'}$ and $Rot_H$. This algorithm shall use one global variable
and all compuation shall be done overwriting values on it. Recursive
calls shall have only constant memory overhead and hence this
algorithm will run in logspace. 

For each step in $G_i$, we need to do $16$ steps in $H$ and $8$ in
$G_{i-1}$. 

\bigskip

The input for $Rot_{G_i}$ is $(\bar{v},\bar{a})$. Let us intepret
$\bar{v}$ as an element of $[N^2]\times [D^{16}]^i$, 
$$
\bar{v} = \parn{v,a_0,a_1,\ldots, a_{i-1}}
$$

Similarly, let us interpret $\bar{a} = a_i$ as an element of
$[D^{16}]$, 
$$
\bar{a} = \parn{k_{i,1},k_{i,2},\cdots, k_{i,16}}
$$
for $k_{i,j} \in [D]$. 

These are written on the input tape as
$$
\begin{array}{|c|c|c|c|c|c|}
\hline
v & a_0 & a_1 & \cdots & a_{i-1} & a_i\\
\hline
\end{array}
$$
which consists of $O(\log N)$ bits. 

\noindent
The algorithm for computing $Rot_{G_i}$ is the following:

%there should be a better way to write this!

\begin{enumerate}
{\item {\bf for} $j=1$ to $16$ {\bf do}
\begin{itemize}
\item {\bf overwrite} $\parn{a_{i-1},k_{i,j}} :=
  Rot_H(a_{i-1},k_{i,j});$
  {\item {\bf If} $j$ is odd 
    \begin{itemize}
    \item {\bf then overwrite} $\parn{v,a_0,\cdots, a_{i-1}} :=
      Rot_{G_i}\parn{v,a_0,\cdots, a_{i-1}};$
    \end{itemize}
  }
  {\item {\bf If} $j = 16$
    \begin{itemize}
    \item {\bf then overwrite} $\parn{k_{i,1},\cdots, k_{i,16}} :=
      \text{{\bf reverse}}(k_{i,1},\cdots, k_{i,16})$
    \end{itemize}
  }
\end{itemize}}
{\item {\bf done}}

\end{enumerate}

The overhead in the recursion is just $j$ since everything else is
maintained in the global worktape. Thus in logspace we can compute the
rotation map of $G_l$. \qed

\bigskip

This concludes Reingold's algorithm and we have proved theorem \ref{reingold}

\newpage
\lecture{ $6$}{V. Arvind}{V. Arvind}{Ramprasad Saptharishi}
\section{Overview}

In the next two lectures we shall discuss a result of Babai and
Szemeridi on random sampling from finite groups. 

{\em There needs to be more introduction, shall be expanded}

\section{The Black-Box Group Model}

You are given a group $G \subseteq \Sigma^m$, considered as strings
over $\Sigma$ and generated by a finite set of generator $S$. You are
also provided an oracle that gives you the necessary group operations,
i.e you can multiply, invert etc but you are not given access to the
actual structure of the operations. 

One could consider the group $G$ to be embedded in a larger group, and
the oracle does the operations on the larger group. Of course with
Cayley's theorem $G\leq S_n$, the permutation group over $n$
elements, but this is too large a group. So usually it's assumed to be
a subset of some matrix group $GL_n(\f_q)$ or something.  \\

\noindent
There are quite a few of problems unlikely to be in $P$, here is an
example. 

\noindent
{\bf Problem: }Given $G=\innerp{A},H=\innerp{B}$, compute $G\bigcap
H$. 

This is known to be harder than graph isomorphism, and there's strong
evidence that this is not $NP-$complete and it is also not known to be
in $P$. \\

Babai and Szemeridi looked at the complexity of {\em Membership
  Testing}, we shall be studying this problem over the next two
lectures.

\section{Membership Testing}

\subsection{The Problem Statement}
$G = \innerp{S}$ and is a subgroup of a matrix group $H = GL_n(\f_q)$ and
you are provided with a black-box for $H$. Given $x$, check if $x\in
G$.\\

We shall that this problem is in $NP\bigcap coAM$. 

\subsection{$MembershipTest \in NP$}

The naive approach is to look at $x$ as a string over $S$ and guess
this string. But one should note that strings could be very large
since the group could be non-commutative. 

However, there should be lots of blocks of repetition  insead the
string representing $x$, and hence rather than asking for the string
one could ask for the {\em circuit} computing $x$ over $S$. Our
circuit would have all nodes to be multiplication gates, with the
elements of $S$ in the leaves and $x$ being the output of the
circuit. Now the question is, if $x\in G$, does there exists a small
circuit for $x$ over $S$?

%a possible diagram maybe

\subsection{Small Circuits for elements of $G$}

\begin{lemma}[Reachability Lemma]
For every $g\in G = \innerp{S}$, there exists a circuit of size
$(1+\log |G|)^2$ that computes $g$ from $S$. 
\end{lemma}

\begin{proof}
Let $x_1, x_2,\cdots, x_i$ be a sequence of group elements. The cube
defined by $\{x_1, \cdots, x_i\}$ is defined as follows.

$$
C\parn{x_1, \cdots, x_i} = \left\{x_1^{e_1}x_2^{e_2}\cdots x_i^{e_i} |
  e_j \in \{0,1\}\right\}
$$


Let $C_0 = C(S) = C(S_0)$. We shall see how we can ``expand'' the cube
to swallow $G$. Let $C_i = C(S_i)$. If $G\subseteq C_i^{-1}C_i$, then
stop; we already have $G$. 

Otherwise, $G\nsubseteq C_i^{-1}C_i$. This means that there exists a
$g_j$ such that $C_i^{-1}C_ig_j \nsubseteq C_i^{-1}C_i$. Hence let
$h_{i+1} \in C_i^{-1}C_ig_j \backslash C_i^{-1}C_i$. Define $S_{i+1} =
S_i \cup {h_{i+1}}$ and $C_{i+1} = C(S_{i+1})$.\\

Now $C_{i+1} = C_i \sqcup C_i\cdot h_{i+1}$ and hence $|C_{i+1}| =
2|C_i|$, and hence in $\log |G|$ steps, we can get $G\in C_i$. Thus
$G$ is a product of $2\log|G|$ elements. What is left to argue is that
the $h_{i+1}$ we've been introducing all the while also has small
circuits. And since we are building on the previous cubes, each
$h_{i}$ needs a circuit of size $2i -1$. 

Hence, for all the $h_{i}$'s we need a circuit of size
$$
\sum_{i=1}^{1+\log|G|} 2i - 1 = \parn{1+\log|G|}^2
$$
as required 

\end{proof}

And now if $x\in G$, the $NP$ machine can guess this circuit for $x$
and check if it infact computes $x$ in polynomial time. Thus
$MembershipTest \in NP$. 

\bigskip

Showing that this is infact in $coAM$ requires a lot more work, we
first need to be able to sample from the group.

\subsection{The Erd\"{o}s and R\'{e}nyi Result}

Here is an informal sketch of the result:

\noindent
{\bf Theorem:}[informal]{\em For any group $G$, ``most'' $O(\log |G|)$
  size sets define cubes that equal $G$. And for $k = c\log |G|$, the distribution
$$
x = x_1^{e_1}x_2^{e_2}\cdots x_k^{e_k}, e_i \in_R \{0,1\}
$$
is ``almost'' uniform, i.e, 
$$
\frac{1 - \epsilon}{|G|} \leq \Pr_{e_1,\cdots, e_k}[x=g] \leq \frac{1+\epsilon}{|G|}
$$
}

The formal version is the following:
\begin{theorem}[Erd\"{o}s and R\'{e}nyi]
  Let $G$ be a finite group and $x = (x_1, \cdots, x_k), x_i\in G$.
  And for all $g\in G$, define

$$
Q_{x}(g) =\Pr_{\bar{e}}[x_1^{e_1}\cdots x_k^{e_k} = g]
$$
Then for all $\epsilon,\delta > 0$, if $k \geq 2\log|G| +
2\log\parn{\frac{1}{\epsilon}} + \log\parn{\frac{1}{\delta}}$, 
$$
\Pr_x\left[\linf{Q_x - U} > \frac{\epsilon}{|G|}\right] \leq \delta
$$
\end{theorem}
\begin{proof} As usual, we shall work with the $L_2$ norm instead of
  the $L_{\infty}$ norm.
\begin{eqnarray*}
\linf{Q_x - U}^2 & \leq & \ltwo{Q_x - U}^2\\
 & = & \sum_g \parn{Q_x(g) - \frac{1}{|G|}}^2\\
\therefore E_x\linf{Q_x - U}^2 & \leq & E_x\ltwo{Q_x - U}^2\\
 & = & \sum_g E_x\parn{Q_x(g)^2 + \frac{1}{|G|^2} -
   2Q_x(g)\frac{1}{|G|}}\\
 & = & E_x\parn{\sum_g Q_x(g)^2} - \frac{1}{|G|}
\end{eqnarray*}
Note that the first term in the last line is the collision
probability. Hence, define $\chi_x(\bar{e},\bar{e'})$ as the indicator
random variable to check for collision, i.e,
$$
\chi_x(\bar{e},\bar{e'}) = 
\begin{cases}
1 & \text{if }x_1^{e_1}\cdots x_k^{e_k} = x_1^{e'_1}\cdots x_k^{e'_k}\\
0 & \text{otherwise}
\end{cases}
$$
Hence, 
\begin{eqnarray*}
E_x\parn{\sum_g Q_x(g)^2} & = & E_x\frac{1}{2^{2k}}
\sum_{e,e'}\chi(e,e')\\
 & = & \frac{1}{2^{2k}} \sum_{e,e'}E_x[\chi_x(e,e')]\\
 & = & \frac{1}{2^{2k}} \sum_{e,e'}\Pr_x[\chi_x(e,e')=1]
\end{eqnarray*}

Now, when $e=e'$, then $\Pr_x[\chi_x(e,e')=1]=1$. As for the other
case when $e\neq e'$, taking all the $e_i$ to one side we have
$\Pr_x[\chi_x(e,e')=1] = \frac{1}{|G|}$. And hence,

\begin{eqnarray*}
E_x\parn{\sum_g Q_x(g)^2} & = & \frac{1}{2^{2k}}\parn{\sum_{e=e'}1} +
\frac{1}{2^{2k}}\parn{\sum_{e\neq e'}\frac{1}{|G|}}\\
& = & \frac{1}{2^k} + \frac{2^{2k} - 2^k}{2^{2k}}\frac{1}{|G|}\\
& = & \frac{1}{|G|} + \frac{1}{2^k}\parn{1 - \frac{1}{|G|}}\\
\therefore E_x\parn{\linf{Q_x - U}^2} & \leq & \frac{1}{2^k}\parn{1 -
  \frac{1}{|G|}}
\end{eqnarray*}

And now to estimate $\Pr_x[\linf{Q_x - U} > \frac{\epsilon}{|G|}]$, we
can use Markov's inequality and the result follows. 
\end{proof}

\subsection{Towards Babai's Sampling Algorithm: The Cayley Graph}

Let $G = \innerp{S}$. The cayley graph $X(G,T)$ where $T = S \cup
S^{-1}\cup \{1\}$ has the vertex set as $G$. And $(x,y)$ is an edge in
the $X(G,T)$ if there exists a $g\in T$ such that $xg=y$.

Earlier we say the following eigenvalue bound
$$
\lambda_2 \leq 1 - \frac{1}{O(diam^2|G|^2)}
$$
In arbitrary graphs, one could have a very small diameter but the size
of the graph could be large (two complete graphs connected by a cut
edge, diameter is $3$ but size is large). But for Cayley graphs, the
additional structure ensure the following eigenvalue bound. 

$$
\lambda_2 \leq 1 - \frac{1}{O(diam^2)}
$$ 

Babai achieves the random sampling by looking at the Cayley Graph as
an expander and taking a random walk on it. Cayley graphs aren't
really expander but they have a property that Babai called the {\em
  Local Expansion Property}.

\begin{lemma}[Local Expansion Lemma]\label{lel_lemma}
Define $T^t$ to be the $t-$neighbourhood of $T$, the set of all
vertices reachable from $T$ by a path of length atmost $t$. Let $0<
\alpha < \frac{1}{2t+1}$, and $D\subseteq T^t$ such that $|D|\leq (1 -
2t\alpha)|G|$. Then there exists a $g \in S$ such that $|D\backslash
Dg| \geq \alpha|D|$
\end{lemma}

Note that if $t$ was the diameter of $X(G,T)$, then $T^t = G$. Taking
$\alpha = \frac{1}{4t}$, we then have for all $D\subseteq G, |D|\leq
\frac{|G|}{2}$, $|\Gamma(D)| \geq \parn{1+\frac{1}{4t}}|D|$, and this
actually gives us that $\lambda_2 \leq 1 - \frac{1}{diam^2}$. 

We shall see the proof of this lemma and the sampling algorithm in the
next lecture. 


\newpage
\lecture{ $7$}{V. Arvind}{V. Arvind}{Ramprasad Saptharishi}


\section{Recap}

Last class we wanted to show that the membership testing problem in
the blackbox group model is in $NP\cap coAM$, and showing it was in
$NP$ was done by construction of small circuits (by expanding
``cubes'') acting as a witness. To show that it is in $coAM$, we
needed to sample from the group; that was the focus of Babai's paper. 

The result of Erd\"{o}s and R\'{e}nyi tells us that given a random set
of size $O(\log |G|)$ can be used to sample almost uniformly at random
from the group $G$. But this would first require to pick the set of
$O(\log|G|)$ elements, which is too costly.

When we noted that Babai then describes the Cayley graph and Lemma
\ref{lel_lemma} tells us that the Cayley Graph has decent expansion
properties, and we shall be exploiting this. As seen in some of our
earlier lecture, we shall analyse random walks on these Cayley
Graphs to help us achieve almost uniform sampling from $G$. 

\section{Proof of Lemma \ref{lel_lemma}}

Suppose the lemma is not true, then for all $g\in S$, $|D\backslash
Dg| < \alpha|D|$. 

\noindent
Now for $x,y\in G$,
\begin{eqnarray*}
D\setminus D_{xy} & \subseteq & (D\setminus D_y)\cup (D_y \setminus
D_{xy})\\
 & = & (D \setminus D_y)\cup(D \setminus D_x)\cdot y\\
\therefore |D\setminus D_{xy}| &\leq &|D\setminus D_x| + |D\setminus
D_y|
\end{eqnarray*}

\noindent
Hence, for all $k$, $u\in T^k$, 
$$
|D\setminus D_u| < k\alpha|D|
$$
Thus for $k=2t+1$,
$$
|D\setminus D_u|<|D|
$$
but this is possible only when $D_u$ contains some elements of $D$,
i.e $D\cap D_u \neq \phi \implies u \in D^{-1}D\subseteq
T^{2t}$ for all $u$, and hence $G = T^{2t}$.

Now lets count the number of pairs $(x,u)$ such that $x\in D, u\in G,
xu \in D$. For every $u\in G$, there exists an $x$ such that $xu\in D$
since $D\cap D_u \neq \phi$. Hence for $k=2t$, 
\begin{eqnarray*}
|D \setminus D_u| &< &2\alpha t|D|\\
\implies |D\cap D_u| &> &(1 - 2\alpha t)|D|
\end{eqnarray*}

And since $|D\cap D_u|$ many $x$'s are possible for each $u$, the total number of
pairs is atleast $(1 - 2\alpha t)|D|\cdot|G|$. 

And also clearly the number of pairs is less than $|D|^2$, which then
forces the contradiction on the size of $D$. \qed

\section{Local Expanders}

In order to study more on the ``local expanders'' we have the
following definition.

\begin{definition}
  Let $X = (V,E)$ any undirected graph and let $Y$ be a vertex induced
  subgraph of $X$. We say $Y$ is $\epsilon$ expanding subgraph of $X$
  if for all $W \subseteq V(Y)$, $|\Gamma_X(W)| \geq (1+\epsilon)|W|$
\end{definition}

\begin{theorem}
If $G = \innerp{S}$ and $X = X(G,T), T = S\cup S^{-1}\cup\{1\}$ then
if $|T^t|\leq \frac{|G|}{2} \implies T^t$ is a $\frac{1}{4t}$
expanding subgraph of $X$, i.e
$$
\forall D\subseteq T^t, |\Gamma(D)| \geq \parn{1+\frac{1}{4t}}|D|
$$
\end{theorem}
\begin{proof}
Put $\alpha = \frac{1}{4t}$ in the earlier lemma and the theorem is done.
\end{proof}

Earlier we had shown that spectral expansion implied vertex
expansion. Here is a result in the other direction, we won't prove it
though. 

\begin{theorem}[Alon's Eigenvalue Bound] Let $G$ be a $d-$regular
  connected non-bipartite undirected graph such that for all
  $U\subseteq V, |U|\leq \frac{|V|}{2}$, $|\Gamma(U)| \geq
  (1+\epsilon)|U|$. Then
  $$
  \lambda_2(G) \leq \parn{d - \frac{\epsilon^2}{4+2\epsilon^2}}\frac{1}{d}
  $$
\end{theorem}

And in the context of locally expanding subgraphs:

\begin{theorem}[Babai's Eigenvalue Bound]
  If $Y$ is an $\epsilon-$expanding subgraph of $X$, then we have the
  following bound for the largest eigenvalue of the adjacency matrix
  (the non-normalized adjacency matrix) of $Y$
  $$
  \lambda_1(Y) \leq d - \frac{\epsilon^2}{4+2\epsilon^2}
  $$
\end{theorem}

Now for random walks on these local expanders.

\begin{theorem}
Suppose we start at a random walk on $X$ from any vertex $v_0\in Y$,
then 
$$
\Pr[\text{the random walk is confined to $Y$ for $l$ steps}] \leq
|V(Y)|e^{-\frac{\epsilon^2 l}{4 + 2\epsilon^2}\frac{1}{d}}
$$
\end{theorem}
\begin{proof}
  Let $A$ be the adjacency matrix of $Y$, and $e_0 \in \R^{|V(Y)|}$,
  the standard basis vector with $1$ at $v_0$ and $0$ everywhere
  else. Assuming that the walk is completely confined in $Y$, the
  transition matrix of the walk is $\frac{1}{d}A$. 

  Now, the probability that you are confined in $Y$ for $l$ steps is
  precisely 
  $$
  (1,1,\cdots, 1)^T\parn{\frac{1}{d}A}^le_0
  $$
  Since $A$ is a real symmetric matrix, we know by the spectral
  theorem that there exists a real eigenbasis. Hence $A = C^TDC$ where
  $C$ is an orthogonal matrix and $D$ is the diagonal matrix of
  eigenvalues. Hence the probability of staying inside $Y$ for $l$
  steps (let me call that value as $P(l)$)
  \begin{eqnarray*}
    P(l) & = & \frac{1}{d^l}\parn{CJ}^T\cdot D^l\cdot \parn{Ce_0}\\
     & \leq & \ltwo{CJ}\cdot \lambda_1^l\ltwo{J}\\
     & = & \parn{\frac{\lambda_1}{d}}^l|V(Y)|
   \end{eqnarray*}
   And now using Babai's eigenvalue bound, the theorem follows.    
\end{proof}

The only other property we need the Cayley graph to satisfy is the
small diameter criteria. Then our random walk would sample almost
uniformly from $G$. 

\begin{claim}
If $diam(G)>2t$, then $|T^t| \leq \frac{|G|}{2}$
\end{claim}
\begin{proof}
If $diam(G)>2t$, then we know that 
\begin{eqnarray*}
G & \nsubseteq & \parn{T^t}^{-1}T^t\\
\implies \exists g & : & T^tg\cap T^t = \phi\\
\implies |T^t| & \leq & \frac{|G|}{2}
\end{eqnarray*}
\end{proof}

Now, suppose $diam(G)>2t$, we know that $|T^t|\leq \frac{|G|}{2}$ and
then, by our earlier theorem, $T^t$ is a $\frac{1}{4t}$ expanding
subgraph of $X(G,T)$. And then, the probability of the random walk
being confined to $T^t$ is upper bounded as follows
$$
P(l) \leq |G| e^{\frac{l}{(64t^2 + 2)|T|}}
$$
And when $l = (64t^2 + 2)|T|\parn{\log|G|}^2$, then $P(l)
\frac{1}{|G|}$ and this $l$ is polynomially bounded in $\log |G|$, so
we are in good shape to emulate the reachability lemma.

Define $R_1 = T$ and for inductive procedures, $C_i = R_1\cdots
R_i$. Suppose $G\subseteq T^{4i}$, we already have small diameter and
hence we are done. 

Suppose $G\nsubseteq T^{4i}$, then $T^{2i}\leq \frac{|G|}{2}$. Do a
random walk for $l$ steps (for the suitable $l$ for $2i$) and add all
the elements visited to $R_{i+1}$.

With good probability, we have an $x \notin C_i^{-1}C_i$ and hence
$|C_{i+1}|\geq 2|C_i|$, the size doubles with each time. Hence with
little error, we would be reaching small diameter in $\log|G|$
steps. 

The accumulated error, by the union bound, is upper bounded by
$\frac{poly(\log|G|)}{|G|}$ and we are in good shape. We can now use
Erd\"os and R\'enyi and we would be able to sample almost uniformly
from $G$.

\section{$MembershipTest \in coAM$}


Needs to be filled out, not sure of it myself. 


\end{document}