\begin{document} \documentclass[11pt]{article} \usepackage{latexsym} \usepackage{amsmath} \usepackage{amssymb} \usepackage{amsthm} \usepackage{hyperref} \usepackage{algorithmic} \usepackage{algorithm} \usepackage{complexity} \usepackage{graphicx} \usepackage{palatino} %my favourite font \usepackage{makeidx} \makeindex \newcommand{\handout}[5]{ \noindent \begin{center} \framebox[\textwidth]{ \vbox{ \hbox to \textwidth { {\bf #2}\hfill {\bf Computational Complexity } } \vspace{4mm} \hbox to \textwidth { {\Large \hfill #5 \hfill} } \vspace{2mm} \hbox to \textwidth { {\em #3 \hfill #4} } } } \end{center} \vspace*{4mm} } \newcommand{\lecture}[4]{\handout{#1}{#2}{Instructor: #3}{Scribe: #4}{#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}[]{Definition} \newtheorem{claim}[theorem]{Claim} \newtheorem{fact}[]{Fact} \newtheorem{subclaim}[theorem]{Subclaim} % 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{\union}{\cup} \newcommand{\Union}{\bigcup} \newcommand{\intersection}{\cap} \newcommand{\Intersection}{\bigcap} \newcommand{\super}[2]{#1^{\inparen{#2}}} %\super{G}{i-1} is G^{(i-1)} \newcommand{\setdef}[2]{\inbrace{{#1}\ : \ {#2}}} \newcommand{\inv}[1]{#1^{-1}} \newcommand{\inrpdt}[2]{\left\langle{#1},{#2}\right\rangle}%\inrpdt{x}{y} is <x,y>. \newcommand{\pderiv}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\iso}{\cong} \newcommand{\bea}[1]{\begin{eqnarray*} #1 \end{eqnarray*}} \newcommand{\legendre}[2]{\inparen{\frac{#1}{#2}}} \newcommand{\zo}{\inbrace{0,1}} \newcommand{\Rot}{\text{Rot}} \newcommand{\tensor}{\otimes} % Commands specific to this file % TODO: Find the right way to typeset group index \DeclareMathOperator{\Sym}{Sym} \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{\llhd}{\!\!\lhd\!\!\lhd} \newcommand{\roundoff}[1]{\left\lfloor #1 \right\rceil} % \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\F}{\mathbb{F}} \newcommand{\N}{\mathbb{N}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Z}{\mathbb{Z}} \renewcommand{\R}{\mathbb{R}} \renewcommand{\C}{\mathbb{C}} %for expected value \newcommand{\Ex}{{\bf E}} %for algorithms \renewcommand{\algorithmicrequire}{\textbf{Input:}} %Dirac's notation \newcommand{\bra}[1]{\left\langle#1\right|} \newcommand{\ket}[1]{\left|#1\right\rangle} %ZigZag Product \newcommand{\zigzag}{\textcircled{z}} \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 Amplification. \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: \begin{enumerate} \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.$ \end{enumerate} 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: \begin{enumerate} \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.$ \end{enumerate} 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 \begin{eqnarray*} \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|} \end{eqnarray*} 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 \begin{eqnarray*} \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}] \end{eqnarray*} 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) Therefore, \begin{eqnarray*} \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 walk}]\\ & = & \frac{1}{4k^2}\frac{t}{|E|}\\ \implies \Ex[N_F] & \geq & \frac{t}{4k^2}\frac{|F|}{|E|} \end{eqnarray*} 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 class. \end{document}