\usepackage{palatino} %my favourite font

        \hbox to \textwidth { {\bf #2}\hfill {\bf Computational Complexity }
        \hbox to \textwidth { {\Large \hfill #5  \hfill} }
        \hbox to \textwidth { {\em #3 \hfill #4} }

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


% my custom commands
\newcommand{\inparen}[1]{\left(#1\right)}             %\inparen{x+y}  is (x+y)
\newcommand{\inbrace}[1]{\left\{#1\right\}}           %\inbrace{x+y}  is {x+y}
\newcommand{\insquar}[1]{\left[#1\right]}             %\insquar{x+y}  is [x+y]
\newcommand{\inangle}[1]{\left\langle#1\right\rangle} %\inangle{A}    is <A>
\newcommand{\abs}[1]{\left|#1\right|}                 %\abs{x}        is |x|
\newcommand{\norm}[1]{\left\Vert#1\right\Vert}        %\norm{x}       is ||x||
\newcommand{\super}[2]{#1^{\inparen{#2}}}             %\super{G}{i-1} is G^{(i-1)}
\newcommand{\setdef}[2]{\inbrace{{#1}\ : \ {#2}}}
\newcommand{\inrpdt}[2]{\left\langle{#1},{#2}\right\rangle}%\inrpdt{x}{y} is <x,y>.
\newcommand{\pderiv}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\bea}[1]{\begin{eqnarray*} #1 \end{eqnarray*}}

% Commands specific to this file
% TODO: Find the right way to typeset group index
\newcommand{\gpidx}[2]{\insquar{#1 : #2}}             %\gpidx{H}{K}   is [H : K]
\newcommand{\gpigs}[2]{\gpidx{\super{G}{#1}}{\super{G}{#2}}} %Group index of g super ...
\newcommand{\roundoff}[1]{\left\lfloor #1 \right\rceil}

% \newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}

%for expected value
\newcommand{\Ex}{{\bf E}}

%for algorithms

%Dirac's notation

%ZigZag Product

\lecture{Gap Amplification}{CS640}{Manindra Agrawal}{Ramprasad Saptharishi}

Last class we concluded by showing that an instance of $G_k$ can be
converted into another instance of $G_k$ with just a constant factor
loss in the gap but making the underlying graph a constant degree
expander. This class we shall look at the third step, which is Gap

\section{Gap Amplification}

Instead of directly constructing the reduction, we shall look at it
with a different perspective. We shall think of the constraints as
being checked by a probabilisitic verifier. The verifier will perform
certain structured random walks to decide whether or not a certain
edge is to be accepted. We shall then see that this can be converted
to a new graph where each walk would correspond to an edge. 

The instance $G$ of $G_k$ is a $(n,d,\lambda)$ expander. Take any
vertex $v\in G$, the number of vertices reachable from $v$ within $t$
steps is at most $d^{t+1}$ since the degree of each vertex is $d.$ We
shall increase the alphabet size to make every vertex hold the colour
of all vertices that are reachable within $t$ steps from it.  The
alphabet size increases from $[1..k]$ to $[1..k]^{d^{t+1}}$ where the
colours of all vertices reachable within $t$ steps (including itself)
is present in its colour. The number of vertices reachable within $t$
steps could be very well under $d^{t+1}$ in which case the superfluous
colours are arbitrary. 

One thing to note is that a vertex $v$ could be reachable from two
vertices $u_1$ and $u_2$ within $t$ steps. Both these vertices might
assign a certain colour to $v$ and in general they may not
coincide. We shall refer to the colour that $u_1$ assigns to $v$ as
$u_1$'s opinion of $v.$ \\

Now for the acceptance criterion. We shall say whether a certain
random walk is accepted or not based on a certain assignment; this
shall be translated to whether a certain edge is accepted or not in
the modified graph as each random would correspond to an edge in the
new graph. The verifier performs a random walk as follows:
\item Pick a random vertex $a\in V.$
\item Pick a random neighbour of $a.$
\item With probability $1/t$, stop.
\item Move to the neighbour and go to step $2.$

The verifier performs such a random walk. If the length of the walk is
larger than $ct$ for a constant $c$ that shall be specified later,
then he accepts. 

Let $a_1,a_2,\cdots, a_l$ be the vertices in the walk. The verifier
reads the colours of $a_1$ and $a_l.$ If $a_1$ and $a_l$ gives
different colours to any $a_i$, the verifier rejects. And for any
intermediate edge $(a_i,a_{i+1})$, if the opinions of the two end
points of the walk violates the constraint in the original graph, the
verifier rejects. If none of the above happened, then he accepts. \\

We need to argue that the verifier will now see a reasonably large
gap. For this purpose, we shall estimate the probability that the
verifier rejects. As usual, we shall pick a colouring assignment to
this new instance and construct a colouring assignment of the old
graph $G.$ This is done by a process similar to the most popular
colour, namely the most popular opinion. However, rather than doing a
naive majority, we shall take a weighted average with the
probabilities. To formalize this notion, we shall define the colour of
a vertex $u$ as follows:
\item Start at the vertex $u.$
\item Pick a random neighbour
\item With probability $1/t$, stop.
\item If length walk equal to  $t$, stop.
\item Move to the neighbour and go to step $2.$
The final vertex now has an associated probability of reaching it. The
most popular colour is now defined as the most probably opinion. 

Let $F$ be the set of violated edges by this colour assignment. What
we know is that $|F| \geq \text{gap}|E|.$ The first thing we need to
do is estimate the number of occurences of a certain edge $e$ in a
random walk.

The expected length of the random walk is $t$ and the probability that
$e$ occurs as the first edge is $1/|E|$ since the initial vertex is
chosen at random by the verifier. Let $X_i$ was the indicator
random variable that takes $1$ if the $i$-th edge is $e$ and $0$ otherwise
\Pr[e\text{ is the $i$-th edge in the walk}] & = & \frac{1}{|E|}\\
\implies \Ex[X_i] & = & \frac{1}{|E|}\\
\implies \Ex\insquar{\sum X_i} & = & \frac{\Ex[\text{length of the walk}]}{|E|}
and hence the expected number of occurances of an edge $e$ in the walk
is $\frac{t}{|E|}.$ We shall use $N$ to denote the length of the walk,
$N_F$ to denote the number of times a violated edge occurs in walk. We
want to estimate $N_F.$ Let $N_{F,e}$ denote the random variables that
counts the number of times the edge $e$, whose constraint should be
violated, appears in the walk. Again, by linearity of expectation:
\Ex[N_F] = \Ex\insquar{\sum N_{F,e}}
And by the definition of expectation
\Ex[N_{F,e}] & = & \sum_{r=1}^{\infty} r\Pr[e\text{ is violated and
number of times $e$ occurs in walk is $r$}]\\
& = & \sum_{r=1}^\infty r\Pr[\text{$e$ is violated $|$ occurs $r$
times}]\Pr[\text{$e$ occurs $r$ times}]
Firstly, the number of times $e$ occurs in the walk is irrelevent to
whether or not $e$ is violated. Therefore, 
\Ex[N_{F,e}] = \sum_{r=1}^\infty r\Pr[\text{$e$ is
violated}]\Pr[\text{$e$ occurs $r$ times}]

(I'm not too clear from this point on, needs some cleaning up. Lack of
clarity begins)

Now to estimate the probability that an edge $e$ is violated, let $e =
(u,v).$ Now look at the walk up till $u,$ reversing this walk gives us
a random walk just as before. So one could think of it as a walk being
performed starting at $u$ and similarly one starting at $v.$ The
probability that these walks have length more than $t$ is $\inparen{1
- \frac{1}{t}}^t$ which is certainly less than half. Therefore, the
probability that the vertex $u$ gets the most popular colour is is at
least $1/2k$ (why?). And similarly, for vertex $v$ as well. 

The next thing to note is that both the vertices $u$ and $v$ are
independently assigned colours. Therefore, the probability that the
constraint $(u,v)$ is violated is at least $\frac{1}{4k^2}$.

(Lack of clarity ends)

\Ex[N_{F,e}] & = & \sum_{r=1}^\infty r\Pr[\text{$e$ is
violated}]\Pr[\text{$e$ occurs $r$ times}]\\
& \geq & \frac{1}{4k^2}\sum_{r=1}r\Pr[\text{$e$ occurs $r$ times}]\\
& = & \frac{1}{4k^2}\Ex[\text{number of times $e$ occurs in the
& = & \frac{1}{4k^2}\frac{t}{|E|}\\
\implies \Ex[N_F] & \geq & \frac{t}{4k^2}\frac{|F|}{|E|}

Thus, in a sense, the verifier sees a new gap of about
$\frac{t}{4k^2}$ on expectation. To argue the probability bounds, we
need a handle on the variance as well. We shall do that in the next