\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 the PCP Theorems} \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}}
\newcommand{\F}{\mathbb{F}}
\begin{document}
\lecture{ $1$}{V. Arvind}{Partha Mukhopadhyay}{Ramprasad Saptharishi}
We shall be following the notes of Venkatesan Guruswami's course
titled ``The PCP Theorems and Hardness of Approximation'', can be
found on his homepage.
\section{The Theorem}
The motivation for this was to look at $NP$ and other classes as a
proof checking system like the $IP$ characterisation of $PSPACE$ or
the $AM$ characterisation of $BP\cdot NP$. The notion of the {\em
Probabilistically Checkable Proof} systems was first given by
(blah), and they also gave the first proof of the PCP theorem which
characterises $NP$.
\subsection{Definition of a PCP System}
A PCP$(r,p)$ system for a language $L$ is an interactive proof system between a Prover and a
Verifier and is done as follows:
\begin{itemize}
\item $x\in \Sigma^n$ is provided as input
\item Prover does some computation on $x$ and write a proof of length $poly(n)$
\item Verifier does some computation, takes $r(n)$ random bits and probes
the proof at $p(n)$ places. And then does some compution to decide
whether he is accepting the proof or not.
\item {\em Completeness:} If $x\in L$, there exists a proof such that
the verifier will accept it with probability $1$.
\item {\em Soundness:} If $x\notin L$, then whatever proof is given to
the verifier, the verifier rejects with probability $\geq 1/3$
\end{itemize}
\subsection{The Statement of the Theorem}
\begin{theorem}[The PCP Theorem]
For all $L\in NP$, there exists a PCP$(O(\log n), O(1))$ system for
$L$.
\end{theorem}
That is, there exits a proof such that the verifier makes $O(\log n)$
coin tosses and chooses a constant number of bits to probe in the
proof and can provide a complete and sound verification.
\section{The Constraint Graph}
\begin{definition}
$\mathfrak{G}=\parn{G=(V,E),C,\Sigma}, C= \{C_e\}_{e\in E} \subseteq \Sigma \times
\Sigma$ is called a constraint graph, with $C_e$ being the constraints
on every edge as relations over $\Sigma$.
An assignment is a map $\sigma:V\rightarrow \Sigma$ and we say
$\sigma$ satisfies an edge $(u,v)\in E$ if
$\parn{\sigma(u),\sigma(v)}\in C_e$
\end{definition}
\subsection{$GAP\cdot CG_{c,s}(\mathfrak{G})$: The Gap Version}
Given as input is a constraint graph $\mathfrak{G} =
\parn{(V,E),C,\Sigma}$.
\begin{itemize}
\item If there exists an assignment $\sigma:V\rightarrow \Sigma$ such
that it satisfies more than $c$ fraction of edges, output ``YES''
\item If every assignment $\sigma$ satisfies atmost $s$ fraction of
vertices,
\item Output anything otherwise
\end{itemize}
\begin{theorem}[Dinur's Theorem]
$GAP \cdot CG_{1,s}(\mathfrak{G})$ is $NP-$hard for a fixed alphabet
$\Sigma$ and constant $s$.
\end{theorem}
And it is clear that one can amplify this gap to $\frac{1}{2}$ with
$O(\log n)$ random bits, and hence
\begin{claim}
Dinur's Theorem $\implies$ PCP Theorem
\end{claim}
\subsection{Roadmap of Proof of Dinur's Theorem}
To show that $GAP \cdot CG_{1,s}$ is $NP-$hard, we shall reduce graph
three-colourability to to this. The idea is that we can represent the
decision problem of graph three-colourability as a gap problem by
itself; the assignment considered as just the colour of the vertex.
$$
3Colour(G) = GAP\cdot CG_{1,1-\frac{1}{m}}(\parn{G,C,\{1,2,3\}})
$$
where the constraints are just the inequality constraints
($\Sigma\times\Sigma - diag$) and $m = |E|$
Thus the reduction is just amplifying the gap $\parn{1,1-\frac{1}{m}}$
to $(1,s)$. This will be done by applying a partial reduction for
logarithmically many steps.
The partial reduction involves $4$ steps:
\begin{enumerate}
\item {\em Degree Reduction}: Make it a constant degree graph, with not too
much blow up in the size fo the graph. The gap reduces, but only by
a constant factor
\item {\em Expanderize}: Convert the graph to an expander, again with
just constant factor troubles in graph size and gap.
\item {\em Gap Amplification:} This was the innovation of Dinur. You
amplify gap, compensate for the losses in the other 3 steps, but on
the other hand your $\Sigma$ size blows up a lot.
\item {\em Alphabet Reduction:} The alphabet size comes down, finally
gap is now twice the original gap, with not too much blow up in the
size of the graph.
\end{enumerate}
\section{The Reduction}
\subsection{Degree Reduction}
Let $G = (V,E)$ be the graph with the set of constraints being
$C$. For every vertex $v\in V$, blow it up into a cloud of $deg(v)$
many vertices, and embed an $\parn{deg(v),d_0, \lambda_0}$ expander
over the cloud for some predefined $d_0$ and $\lambda_0$.
Now the vertex set cardinality of the new graph is $\sum deg(u) =
2|E|$, and the edge set cardinality is $|E| + \sum\frac{deg(u)d_0}{2}
= |E|(1+d_0)$. As for the constraints, retain the edge constraints to
the appropriate edges in the new graph, and equality constraints
within each cloud. We then have a constant degree constraint graph
over the same alphabet.
Of course, we want the gap to be respected. Define $gap = $fraction of
edges unsatisfied by the best assignment. Let the gap of $G$ be $gap$
and that of the new graph is $gap'$. Clearly $gap = 0 \implies gap'
=0$, but we don't want to lose much on any non-zero gap.
\begin{claim}
If $gap \neq 0$, $gap' \geq \frac{gap}{O(1)}$
\end{claim}
\begin{proof}
Let $\sigma'$ be the best assignment for $G'$. Define an assignment
$\sigma$ for $G$ as $\sigma(v) = maj(\sigma'(u))$ over all $u\in
cloud(v)$. Let $|F|$ be the set of edges violated by $\sigma$, then
clearly $gap \leq \frac{|F|}{|E|}$.
Let $e=(u,v)\in F$, and let $e' = (u',v')$ be the corresponding intercloud edge
in $G'$. And let $S_u = \{v\in cloud(u)|\sigma'(v)\neq
\sigma(u)\}$. Now either $\sigma'$ satisfies $e'$ or it doesn't.
Suppose $\sigma'$ satisfies $e'$, then either $u'\in S_u$ or $v'\in
S_v$ since otherwise $e'$ would be satisfied. Hence we have
$$
gap|E| \leq gap'|E'| + \sum_{u\in V}|S_u|
$$
\begin{itemize}
{\item Case 1: if $gap'|E'| \geq \frac{gap|E|}{2}$, then we are done
since
$$
gap' \geq \frac{gap|E|}{2|E|(1+d_0)} = \frac{gap}{2(1+d_0)} = \frac{gap}{O(1)}
$$
}
{\item Case 2: Otherwise, $\sum |S_u| \geq \frac{gap|E|}{2}$. Let
$S_u^a$ be the set of vertices in $S_u$ that are coloured $a$ by the
assignment $\sigma'$.
Clearly $|S_u^a| \leq \frac{1}{2}|cloud(u)|$, and since $cloud(u)$
is an expander, there exists $c|S_u^a|$ many edges going out of
$S_u^a$ for some appropriate $c$. And all these edges are violations
since we have forces equality constraints over the intracloud edges.
Thus counting the number of unsatisfied edges,
$$
|F'| = gap'|E'| \geq c\sum_{u\in V}|S_u^a| \geq \frac{c}{2}gap|E|
$$
and we then have that $gap' = \frac{gap}{O(1)}$}
\end{itemize}
\end{proof}
Hence we now have a constant degree graph with decent gap.
\subsection{Expanderize}
We have our graph $G$ to be a $d$-regular graph with $n$ vertices. Now
take a $H = (n,d_0,\lambda_0)$ expander ($\lambda_0$ is the second
largest eigenvalue of the non-normalized adjacency matrix) for
suitable parameters and just superimpose on $G$.
The adjacency matrix (non-normalized) is clearly satisfies
$$
A_{G'} = A_G + A_H
$$
And by the Rayleigh characterisation of the second largest eigenvalue,
the second largest eigenvalue of the non-normalized adjacency matrix
of $G'$:
$$
\lambda_2(G') \leq d + \lambda_H < d + d_0
$$
and hence $G'$ is an expander.
As for the new constraints, just add trivial (always true) constraints
on the new edges. the size of the edge set $|E'| = |E| +
\frac{nd_0}{2} = \frac{n(d+d_0)}{2}$ and
$$
gap' = \frac{gap |E|}{\frac{n}{2}(d+d_0)} = \frac{gap}{O(1)}
$$
Hence we now have reduced the generalised gap version to a special
case on constant degree expanders.
\subsection{Gap Amplification: a sketch}
$G$ is a $(n,d,\lambda)$ expander. Fix a parameter $t$, the value
shall be chosen later. The new constraint graph has the same set of
vertices, $\Sigma' = \Sigma^{1+d+\cdots + d^t}$ and edges in the new
graph are vaguely like $t$ step walks in $G$.
For every $u\in V$, it can reach $1+d+\cdots + d^t$ vertices in a $t$
step walk, vertices counted with repetition. In this context, an
assignment $\sigma':V\rightarrow \Sigma'$ can be thought of as a
vector with $1+d+\cdots +d^t$ coordinates where each coordinate
$\sigma(u)_v$ can be thought of $u$'s opinion about $v$.
The constraints are the following, for every edge $e = (a,b)$, it can be
intepretted as a $t$ step walk from $a$ to $b$. For every $(u,v)$ in
the $t$-walk, check if $(\sigma'(a)_u,\sigma'(b)_v)$ must be in $C_e$
of the input graph.
Now, suppose $\sigma'$ is the best assignment, we shall again extract
a $\sigma$ for $G$. Look at all the vertices that could have an
opinion about $u$, and take the majority of the opinions.
Let $F$ be the set of unsatisfied edges in $G$ with respect to
$\sigma$, and $gap'$ the new gap.
$$
gap' = \Pr_{e'}[e' \text{ is rejected under }\sigma']
$$
By the way we've chosen our $\sigma$, there is a ``good'' chance that
$\sigma'(a)_u = \sigma(u)$ and $\sigma'(b)_v = \sigma(v)$. Hence if
$(u,v)\in F$, there is a good chance that $e'$ contains the edge
$(u,v)$ to be rejected.
Roughly speaking,
$$
gap' \geq \frac{1}{O(1)} \Pr_{e'}[e' \text{ passes through }F]
$$
Since we have an underlying expander, missing $|F|$ is ``rare''
\begin{eqnarray*}
gap' & \geq & \frac{1}{O(1)}\parn{1 - \parn{1 - \frac{|F|}{|E|}}^t}\\
& \geq & \frac{t}{O(1)} \frac{|F|}{|E|}
\end{eqnarray*}
and $t$ is chosen such that the amplification, taking into account the
losses in the other steps, is $geq 2$.
But our alphabet is now $\Sigma^{d^{t+1}}$, and thus we need to reduce
the alphabet size back to $\Sigma$, which is the next sub-routine in
the reduction.
\newpage
\lecture{ $2$}{V. Arvind}{Partha Mukhopadhyay}{Ramprasad Saptharishi}
\section{Overview}
This class we shall look at the gap-amplification routine. This isn't
the original method that Dinur adopted in her paper, this was
suggested by Jaikumar Radhakrishnan by considering some special kinds
of random walks
\section{Gap Amplification}
\subsection{Lazy Random Walks}
Let $G(V,E)$ be a $d$-regular graph. We can then talk of two kinds of
random walks:
\begin{enumerate}
\item {\em After stopping random walk} (ASRW): Follows the subroutine
\begin{enumerate}
\item Pick $v\in V$ at random
\item Take a random step
\item Stop there with probability $\frac{1}{t}$
\item Go to step $(b)$.
\end{enumerate}
\item {\em Before stopping random walk} (BSRW): Given a start vertex
$v$, follows the subroutine
\begin{enumerate}
\item Stop at $v$ with probability $\frac{1}{t}$
\item Take a random step
\item Go to step $(a)$
\end{enumerate}
\end{enumerate}
It's clear that the length of an ASRW is atleast $1$ whereas that of a
BSRW could be $0$ as well. And also, every ASRW walk stops after
finitely many steps\footnote{one can easily show that probability of
any infinite long ASRW is $0$}.\\
Let $(u,v)$ be some edge and $Y$ be the random variable that counts
the number of $u-v$ moves in an ASRW. Suppose you are given a promise
that the edge is traversed $k$ times, we want to estimate the
distributions on the end points of the random walk, that is $\Pr [b=w
| Y=k]$ where $b$ is the end of the walk.
Before we actually get to this, let us look at $\Pr [b=w | Y \geq k]$,
when the edge is traversed atleast $k$ times. Once we've made the
$k$-th move on $(u,v)$, the rest is just a BSRW starting at $v$!
Hence for every $w\in V$,
$$
\Pr[b=w | Y \geq k] = P_{v,w}
$$
where $P_{v,w}$ is probability of reaching $w$ from $v$ through a
BSRW.
And turning the walk around, we can also see that for all $w'\in V$
$$
\Pr[a=w'| Y\geq k] = P_{w',u}
$$
Now,
\begin{eqnarray*}
P_{v,w}=\Pr[b=w|Y \geq k] &= &\frac{\Pr[b=w\wedge Y\geq k]}{\Pr[Y\geq k]}\\
& = & \frac{\Pr[b=w \wedge Y=k] + \Pr[b=w|Y\geq k+1]}{\Pr[Y=k]+
\Pr[Y\geq k+1]}\\
& = & \parn{\frac{\Pr[b=w\wedge Y=k]}{\Pr[Y=k]} + \frac{\Pr[b=w \wedge
Y\geq k+1]}{\Pr[Y\geq k+1]}}/\parn{\frac{\Pr[Y=k]}{\Pr[Y\geq k+1]}
+ 1}\\
& = &\parn{\frac{\Pr[b=w\wedge Y=k]}{\Pr[Y=k]} + P_{v,w}}/ \parn{\frac{\Pr[Y=k]}{\Pr[Y\geq k+1]}}
\end{eqnarray*}
and with some cross-multiplication and cancelling, we get
$$
\frac{\Pr[b=w\wedge Y=k]}{\Pr[Y=k]} = \Pr[b=w|Y=k] = P_{v,w}
$$
and similarly for $w'$. This then shows that the conditioned on a
fixed edge being traversed $k$ times, the end points of the AFRW are
independantly distributed.
\subsection{The Amplification Process}
The reduction procedure would be a little different, we shall consider
a randomized verifier who is constructing the new graph $G'$ from
$G$. Later we shall remove the randomness to get our deterministic
polynomial time reduction. \\
The input is the constraint graph on $G=(V,E)$ which is a
$(n,d,\lambda)$ expander with alphabet $\Sigma$ and gap as $gap$. We
want to get a new graph $G'=(V,E')$ with new constraints and alphabet
as $\Sigma' = \Sigma^{1+ d + \cdots + d^t}$ for a parameter $t$ which
shall be chosen later.\\
\noindent{\bf Verifier's Procedure:}
\begin{itemize}
\item Do an ASRW on the graph $G$ for $t$ steps, let the start vertex
be $a$ and the end vertex be $b$.
\item The edge $(a,b)$ is given weight $P_{a,b}$, the probability of
the ASRW starting at $a$ and ending at $b$.
\item The edge $(a,b)$ is given the constraints as follows for any
assignment $\sigma: V\rightarrow \Sigma^{1+d+\cdots + d^t}$:
For every edge $(u,v)$ in the ASRW, $(\sigma'(a)_u,\sigma'(b)_v)$
should be satisfied in the old graph.
\end{itemize}
The problem with this is that we now have a complete graph on $V$,
with the probabilities of choosing them as the weights. This is too
costly since we need to do this reduction for $O(\log n)$ steps and we
can't have anything more than $|E'| = O(1)|E|$. This problem howeever
will be fixed later.
\subsection{Lowerbounding $gap'$}
Let $\sigma':V\rightarrow \Sigma'$ be the best assignment for $G'$. We
shall extract an assignment for $G$ to get an upperbound on $gap'$.
$\sigma(u)$ is defined as follows:
\begin{itemize}
\item Do a BSRW starting at $u$. This generates a probability
distribution $X(v)$ on the vertices reachable from $u$ with a path of
length atmost $t$.
\item For all $a\in \Sigma$, let
$$P_a = \sum_{\sigma'(v)_u = a} X(v)$$
Define $\sigma(u)=c$ such that $P_c = max_{a\in \Sigma}P_a$, the
``most frequent opinion of $u$ from other vertices''.
\end{itemize}
Let $F$ be the set of unsatisfied edges, we may throw in some more
unsatisfied edges so that $gap = \frac{|F|}{|E|}$
\begin{definition}
A $u\rightarrow v$ step in the verifier's $a\rightarrow b$ walk is
said to be faulty if
\begin{itemize}
\item $(u,v)\in F$
\item $dist(a,u)\leq t$ and $\sigma'(a)_u = \sigma(u)$
\end{itemize}
\end{definition}
Let $N$ be the random variable that counts the number of faulty steps
in the verifier's walks. And clearly $gap' \geq Pr[N\geq 0]$
\begin{lemma}
$$
E[N] \geq \frac{t}{8|\Sigma|^2}\frac{|F|}{|E|}
$$
\end{lemma}
\begin{proof}
Let $(u,v)\in F$. Clearly it's enough to show that the expected
value of $u\rightarrow v$ faulty steps (say $N_{uv}$) is bounded
below by $\frac{t}{8|\Sigma|^2}\frac{1}{|E|}$
$$
E[N_{uv}] = \sum_{k\geq 1} k\Pr[u\rightarrow v \text{ is faulty}|k\
(u\rightarrow v) \text{steps}]\Pr[k\ (u\rightarrow v) \text{steps}]
$$
\begin{claim}
$
\Pr[(u\rightarrow v) \text{ is faulty}|k\ (u\rightarrow v)
\text{steps}] \geq \frac{1}{4|\Sigma|^2}
$
\end{claim}
\noindent{\em Pf:} The required probability is just checking
\begin{enumerate}
\item $dist(a,u) \leq t$ and $\sigma'(a)_u = \sigma(u)$
\item $dist(b,v) \leq t$ and $\sigma'(b)_v = \sigma(v)$
\end{enumerate}
But these two are independant distributions given the promise that the
edge $(u,v)$ is traversed $k$ times. So $\Pr[1 \vee 2] = \Pr[1] + \Pr[2]$
$$
\Pr[\sigma'(b)_v = \sigma(v)|dist(b,v)\leq t]\cdot \Pr[dist(b,v)\leq t]
$$
By our choice of $\sigma(u)$, $\Pr[\sigma'(b)_v =
\sigma(v)|dist(b,v)\leq t] \geq\frac{1}{|\Sigma|}$
And
\begin{eqnarray*}
\Pr[dist(b,v)\leq t] & = & \Pr[b \text{ is generated within }t\text{
steps}]\\
& = & 1 - \parn{1 - \frac{1}{t}}^t\\
& > & 1 - \frac{1}{e}\\
& > & \frac{1}{2}
\end{eqnarray*}
And together with the two bounds, the claim is done. \qed\\
And thus with this claim,
\begin{eqnarray*}
E[N_{uv}] & \geq &\frac{1}{4|\Sigma|^2} E[\text{number of $(u,v)$
steps}]\\
E[\text{number of $(u,v)$ steps}] & = & \sum_{k\geq 1} E[\text{number
of $(u,v)$ edges}|\text{$k$ steps in walk}]\Pr[\text{$k$ steps in
walk}]
\end{eqnarray*}
Now for any $d$-regular graph, after starting with the uniform
distribution on the vertices, after an $i$ step random walk, the
probability of traversing any edge is $\frac{1}{2|E|}$ for every $i$.
Hence,
\begin{eqnarray*}
E[\text{number of $(u,v)$ steps}] &= &\frac{1}{2|E|t}\sum k\parn{1 - \frac{1}{t}}^{k-1}\\
& = & \frac{1}{2|E|t}\parn{1-\parn{1-\frac{1}{t}}}^{-2}\\
& = & \frac{t}{2|E|}\\
\therefore E[N_{uv}] & \geq & \frac{1}{4|\Sigma|^2}\cdot \frac{t}{2|E|}
\end{eqnarray*}
and summing over every edge $(u,v)\in F$, the lemma is proved.
\end{proof}
Before we go further in bounding $gap'$, let us first prune the graph down.
\subsection{Pruning down the graph}
We have a complete graph because the verfier is able to look at all
paths and hence we have all edges in $G'$. The natural thing to do is
to cut down the verifier's walks.
\noindent{\bf Modified Verifier:} Fix a parameter $B = ct$
\begin{itemize}
\item If the verifier makes more than $B$ steps, put no constraint on
$(a,b)$.
\item Otherwise use the same test as in the earlier veifier.
\end{itemize}
Throw away all unconstrained edges from $G'$. It's clear that the
degree of this graph is bounded by $1+d+ \cdots d^B$ and $size(G')
\leq c'size(G)$. Probabilities are rational numbers with the
numerators and denominators depending on $B$ and $t$ alone and hence
the weights(probabilities) can be removed by having multiple edges.
Now we shall argue that the bounds on $gap'$. Let $\sigma'$ be the
best assignment for $G$, we shall extract $\sigma$ just as in the
earlier case, by considering the most frequent opinion. Again, we can
throw some unsatisfied edges to make $gap = \frac{|F|}{|E|}$.
\begin{definition}A $u\rightarrow v$ step is said to be $faulty'$ if
it is faulty and the verifier stops within $B$ steps in that walk.
\end{definition}
Let $N'$ be the random variable that counts the $faulty'$ steps, and
let $N_F$ be the random variable that counts the number of times the
walk passes through $F$ and let $S$ be the number of steps. We need to
argue that $\Pr[N'>0]$ is large.
\begin{theorem}[Second Moment Method] For any random variable $N$,
$$
\Pr[N>0] \geq \frac{E[N]^2}{E[N^2]}
$$
\end{theorem}
\noindent The proof of this theorem is left as an exercise. \\
Now for a similar lemma as in the earlier case.
\begin{lemma}
$$
E[N'] \geq \frac{t}{16|\Sigma|^2}\cdot \frac{|F|}{|E|}
$$
\end{lemma}
\begin{proof}
$E[N'] = E[N] - E[N|S>B]\Pr[S>B]$ and we know that $\Pr[S>B] =
\parn{1-\frac{1}{t}}^B$. And again by the same argument used
earlier, we get
\begin{eqnarray*}
E[N|S>B] &= &\parn{\sum_{k\geq 1} (B+k)\frac{1}{2|E|} \parn{1 -
\frac{1}{t}}^{k-1}\frac{1}{t}}|F|\\
& =& \frac{B+t}{2|E|}|F|\\
\therefore E[N|S>B]\Pr[S>B] &\leq
&e^{-B/t}\parn{\frac{B+t}{2|E|}|F|}
\end{eqnarray*}
Now we can choose $c$ appropriately and be done.
\end{proof}
\bigskip
Now, we need to bound $E[N'^2]$. Let $\chi_i$ be the indicator random
variable that checks if the $i^{th}$ step of the verifier is in $F$.
It is clear that $N'\leq N_F$ and hence $E[N'^2] \leq E[N_F^2] = \sum
E[\chi_i \chi_j]$. Hence
\begin{eqnarray*}
E[N'^2] & \leq & 2 \sum_{i,j} E[\chi_i \chi_j]\\
& \leq & 2\sum_i \Pr[\chi_i = 1] \cdot \sum_{j\geq
i}\Pr[\chi_j=1|\chi_i=1]
\end{eqnarray*}
\noindent
When $i=j$, $\Pr[\chi_j=1|\chi_i=1]=1$, otherwise, it is equal to
\begin{eqnarray*}
\Pr[\text{a walk starting from an endpoint on $F$ takes its
$(j-i)^{th}$ edge in $F$}]\\
\times\Pr[\text{the walk takes atleast $j-i$ more steps}]
\end{eqnarray*}
The second term we know is equal to $\parn{1 - \frac{1}{t}}^{j-i}$,
the bound for the first term follows from the following expander
lemma.
\begin{lemma}
Let $G=(n,d,\lambda)$ expanderand $F\subseteq E$. Then the probability
that a random walk with initial step in $F$ will move in $F$ at the
$l^{th}$ step is
$$
\leq \parn{\frac{|F|}{|E|}+\parn{\frac{\lambda}{d}}^{l-1}}
$$
\end{lemma}
\begin{proof}
The proof is exactly like the proof of the mixing time lemma, same
adjacency matrix trick.
\end{proof}
Hence taking $j-i=l$,
\begin{eqnarray*}
E[N'^2] & \leq & 2\sum_i \Pr[\chi_i=1]\parn{1 + \sum_l
\parn{1-\frac{1}{t}}^l\parn{\frac{|F|}{|E|}+
\parn{\frac{\lambda}{d}}^{l-1}}}\\
& \leq & 2\sum_i \Pr[\chi_i =1]\parn{1 + (t-1)\frac{|F|}{|E|} +
O(1)}\\
\end{eqnarray*}
The $O(1)$ comes in because $d$ and $\lambda$ are constants which are
fixed earlier. Now we can assume that $\frac{|F|}{|E|} \leq
\frac{1}{t}$, otherwise we already have attained constant gap.
\begin{eqnarray*}
E[N'^2] & \leq & O(1)\sum_i \Pr[\chi_i = 1]\\
& = & O(1)E[N_F]\\
& \leq & O(1)t\frac{|F|}{|E|}
\end{eqnarray*}
And now using our second moment method, we have
$$
\Pr[N'>0] \geq \frac{t}{O(1)}\frac{|F|}{|E|}
$$
\indent
and we are through with gap-amplification.
\newpage
\lecture{ $3$}{V. Arvind}{Bireswar Das }{Ramprasad Saptharishi}
\section{Overview}
We are not at the last step of the subroutine that achieves the
reduction to prove Dinur's Theorem. We would be applying the routine
for $O(\log n)$ steps and hence this clearly means that the alphabet
can't be as large as it is at the end of step $3$. Our goal is to now
reduce the alphabet size down to a constant without losing the
amplification achieved. \\
We would need a lot of machinary for this step, the crux is the {\em
Assignment Tester}.
\section{Assignment Tester $\implies$ Alphabet Reduction}
\begin{definition}A $q$-query assignment tester $AT(\gamma>0, \Sigma)$
is a reduction algorithm $P$ whose input is a boolean circuit $\Phi$
over $X$ and outputs a system of constraints $\Psi$ over $X$ and a
set of auxillary variables $Y$ such that:
\begin{itemize}
\item $Y$ takes values from $\Sigma$
\item Each constraint $\psi\in \Psi$ depends on atmost $q$
variables.
\item For all $a:X\rightarrow \{0,1\}$
\begin{itemize}
\item If $\Phi(a)=1$, then there exists an assignment
$b:Y\rightarrow \Sigma$ such that $a\cup b$ satisfies all
constraints $\psi\in \Psi$
\item If $a$ is $\delta$-far\footnote{by the relative hamming
distance} from any satisfying assignment of $\Phi$, then for every
assignment $b:Y\rightarrow \Sigma$, $a\cup b$ violates atleast
$\gamma\delta$ fraction of the constraints.
\end{itemize}
\end{itemize}
\end{definition}
But in order to use this in our constraint graphs, we need a $2$-query
assignment tester since each constraint is an edge in the constraint
graph.
And from the definition if the $\Phi$ was satisfiable then $gap=0$ for
the constraints. And if the $\Phi$ was not satisfiable, then every
assignment is $1$-far from a satisfying assignment (since there aren't
any satisfying assignments) and hence the gap is atleast
$\gamma$. This is just like the PCP reduction, except for the running
time of the assignment tester, which could potentially be
exponential.
But we can apply this assignment to only some small circuits of the
graph, and help is reduce the alphabet size.
\begin{theorem}[Composition Theorem] Let $P(\gamma>0, \Sigma_0)$ be a
$2$-query assignment tester. Then for any constraint graph
$\mathfrak{G}=(G,C,\Sigma)$ can be converted, in polynomial time, to
another constraint graph $\mathfrak{G'}=(G',C',\Sigma_0)$ such that:
\begin{itemize}
\item $size(G') \leq O(1)size(G)$
\item $gap(G) =0 \implies gap(G')=0$
\item There exists a $\beta>0$, depending only on $P$ and $|G|$, such
that $gap(G')\geq \beta\cdot gap(G)$
\end{itemize}
\end{theorem}
\begin{proof}
The idea is to apply $P$ on each constraint on the edges to transform
the graph into another constraint graph. First we need to give $P$ a
circuit, so we shall encode the elements of $\Sigma$ as binary
strings by using an error correcting code.
Let $e:\Sigma \rightarrow \{0,1\}^l$ be a constant rate code, (i.e) $l
= O(\log |\Sigma|)$ and minimum distance being $\rho = \frac{1}{4}$,
that is $x\neq y \implies \Delta(e(x),e(y))\geq \rho\cdot l$.
Our constraint graph is $(G=(V,E),\mathcal{C}, \Sigma)$, for each
constraint $c\in \mathcal{C}$ on the variable $u,v$ of $G$, define a
new constraint on $[u]\cup [v]$, where $[u]$ is the encoding of $u$
under $e$, as follows:
$\Phi_{u,v}(a,b)=1$ if and only there exists $\alpha,\alpha' \in
\Sigma$ such that $e(\alpha) = a$, $e(\alpha')=b$ and $c(\alpha,
\alpha')=1$ for all constraints $c$ on the edge $(\alpha, \alpha')$.
We can then interpret $\Phi_{u,v}:\{0,1\}^{2l} \rightarrow \{0,1\}$ as a
boolean circuit and feed it to the $2$-query assignment tester. The
output obtained will now be a list of constraints $\Psi_{u,v}$, each
dependant on just two variables. And hence this can be interpretted as
a constraint graph over $\Sigma_0$, say $(G_{u,v} = (V_{u,v}, E_{u,v}),
\mathcal{C}_{u,v})$ such that $[u]\cup [v] \subseteq V_{u,v}$. Our new
constraint graph $(G'=(V',E'),\mathcal{C}',\Sigma_0)$ will just be
these small constraint graphs pasted together.
\begin{itemize}
\item $V' = \bigcup_{e\in E} V_e$
\item $E' = \bigcup_{e\in E} E_e$
\item $\mathcal{C}' = \bigcup_{e\in E} \mathcal{C}_e$
\end{itemize}
Now we need to show that this graph proves the theorem. Firstly, the
size bound of $G$ is clear since each edge of $G$ is blown up by the
output of the assignment tester's output on the constraints. And
since, with possible addition of multiple edges, each $G_c$ is of
equal size the size of $G'$ is clearly $O(1)size(G)$; and is also
clear that this can be done in polynomial time. \\
When $gap(G)=0$, we have a satisfying assignment to our input circuit
to the assignment tester. Hence by definition of the assignment
tester, $gap(G')=0$.
As for the other case, let $\sigma':V'\rightarrow \Sigma_0$ be the
best assignment. From this, extract an assignment
$\sigma:V\rightarrow \Sigma$ as follows:
$$
\sigma(u) = \text{arg}\min_a(\sigma'([u]), e(a))
$$
that is, pick the nearest codeword to the label. There is a catch,
$\sigma'$ should assign $\{0,1\}$ values for $[u]$ for all $u\in V$,
but that has to happen since any other value would only make more
constraints unsatisfied.
Atleast $gap(G)\cdot |E|$ edges have to be violated in the old
graph; we now want to count the number of violations in $G'$. Let
$(u,v)$ be violated by $\sigma$.
\begin{claim}
$\sigma'([u])\cdot \sigma'([v])$ is atleast $\frac{\rho}{4}$-far
from any satisfying assignment for the constraint circuit
$\Phi_{u,v}$ of the edge $(u,v)$
\end{claim}
\begin{proof}
Let $(e(a),e(b))$ be the satisfyign assignment for $\Phi_{u,v}$ that
is closest to $\sigma'([u])\cdot\sigma'([v])$; this forces
$c(a,b)=1$ for all constraints $c$ on the edge. Hence, either $a\neq
\sigma(u)$ or $b\neq \sigma(v)$ otherwise it would contradict the
assumption that $(u,v)\in F$. Without loss of generality, let us
assume that $a\neq \sigma(u)$. Then
\begin{eqnarray*}
\rho & \leq & \Delta\parn{e(a), e(e(u))} \\
& \leq & \Delta\parn{e(a), \sigma'([u])} + \Delta\parn{\sigma'([u]),
e(e(u))}\\
& \leq & 2\Delta\parn{e(a),\sigma'([u])}
\end{eqnarray*}
And since we have a concatenation of $\sigma'([u])$ and
$\sigma'([v])$, it has to be atleast $\frac{\rho}{4}$-far from any
satisfying assignment for $\Phi_{u,v}$
\end{proof}
Hence the $\sigma'$ violates atleast $\gamma\cdot \frac{\rho}{4}$
fraction of the constraints in each such $G_{u,v}$ and hence violates
$gap(G)\gamma\cdot \frac{\rho}{4}$ fraction of constraints in $G'$ and
thus proves the theorem with $\beta = \gamma\cdot \frac{\rho}{4}$
\end{proof}
\section{In Search of an Assignment Tester}
Once we have a $2$-query assignment tester, then by the earlier
theorem we are done. Infact, the following theorem tells us that
finding a $q$-query assignment tester over $\Sigma=\{0,1\}$ would be
enough.
\begin{theorem}
Let $P$ be a $q$-query $(\gamma, \{0,1\})$ assignment tester. Then
we can onstruct a $2$-query $(\frac{\gamma}{q},\{0,1\}^q)$
assignment tester from $P$.
\end{theorem}
\begin{proof}
On an input $\Phi$ over $X$, let $P$ output $\Psi$ as the set of constraints
over the variables $X\cup Y$. We shall define the $2$-query assignment
tester as follows:
\begin{itemize}
\item The auxillary variables are $Y\cup Z$ where $Z = \{z_\psi|\psi
\in \Psi\}$ over the alphabet $\{0,1\}^q$
\item For each constraint $\psi\in \Psi$, we add $q$ constraints as
follows. Let $v_1, \cdots, v_q$ be the inputs that $\psi$ depends on
(repeat something if less). Add the constraint $(z_\psi, v_i)$ for
every $1\leq i\leq q$ such that it is satisfied by $(a,b)$ if the
assignment $a$ ($\in \{0,1\}^q$) satisfies $\psi$ and the value that
$a$ gives to $v_i$ is $b$.
\end{itemize}
Hence, any assignment that satisfies everything in $\Psi$ can be
clearly extended to satisfy every constraint in the $2$-query
assignment tester's output. And since we are spreading every
constraint over $q$ $2$-query constraints, an assignment that is
$\delta$-far from a satisfying assignment will violate $\frac{\gamma
\delta}{q}$ fraction of constraints.
\end{proof}
We shall construct a $6$-query assignment tester and this shall then
give us a $2$-query assignment tester over the alphabet $\Sigma_0$
such that $|\Sigma_0|=64$. We would require a lot of machinary before
that.
\section{Linearity Testing}
\begin{definition}A function $f:\{0,1\}^n\rightarrow \{0,1\}$ is said
to be a linear function if there exists $S\subseteq [n]$ such that
$f(x) = \oplus_{i\in S} x_i$
\end{definition}
This basically means that for all $x,y\in \{0,1\}^n$, $f(x\oplus y) =
f(x)\oplus f(y)$. \\
\noindent
For every $S\subseteq [n]$, let $\chi_S:\{0,1\}^n \rightarrow \{0,1\}$
be defined as $F_S(x) = \oplus_{i\in S}x_i$. Given an input function
$f$, the linearity test tries to distinguish the two cases:
\begin{itemize}
\item $f$ is equal to $\chi_S$ for some $S\subseteq [n]$
\item $f$ is ``far'' from every $\chi_S$
\end{itemize}
\subsection{The Blum-Luby-Rubinfeld Test}
\begin{definition}Two functions $f$ and $g$ from are said to be
$\delta$-far if
$$
\Pr_x[f(x)\neq g(x)]\geq \delta
$$
They are said to be $\delta$-close if
$$
\Pr_x[f(x)\neq g(x)]\leq \delta
$$
\end{definition}
\noindent
{\bf BLR Test:}
Input $f:\{0,1\}^n\rightarrow \{0,1\}$
\begin{enumerate}
\item Pick $x,y\in_R \{0,1\}^n$
\item Accept if $f(x\oplus y)=f(x)\oplus f(y)$, reject otherwise.
\end{enumerate}
\begin{claim}[BLR Completeness]
If $f$ is linear, BLR always accepts
\end{claim}
\begin{proof} Clear! \end{proof}
\begin{claim}[BLR Soundness]
If $f$ is $\delta$-far from any linear function, then BLR rejects with
probability $\geq\delta$
\end{claim}
\begin{proof} We shall do a fourier analysis on the function for the
proof. First we shift our notation from $\{0,1\}$ to $\{-1,1\}$, thus
each $\chi_S(x) = \prod_{i\in S} x_i$
\begin{eqnarray*}
\Pr[\text{BLR rejects}]& =&\Pr_{x,y}[f(x)f(y)\neq f(xy)]\\
& = & E_{x,y}\left[ \frac{1-f(x)f(y)f(xy)}{2}\right]
\end{eqnarray*}
It is easy to see that $\{\chi_S\}_{S\subseteq [n]}$ forms an
orthonormal basis for the set of boolean functions under the
following inner product definition:
$$
\innerp{f,g} = \frac{1}{2^n}\sum_x f(x)g(x)
$$
And hence, every boolean function $f$ can be written as
$$
f(x) = \sum_S f_S \chi_S(x)
$$
and the coefficients $f_S$, under this basis, are called the fourier
coefficients. And by Parseval's identity, $\sum_S f^2_S = 1$
\begin{eqnarray*}
E_{x,y}[f(x)f(y)f(xy)] & = & E\left[\sum f_S\chi_S(x)\sum f_T \chi_T(y)
\sum f_T \chi_T(xy)\right]\\
& = & E\left[\sum f_S f_T f_U \chi_S(x)\chi_T(y)\chi_U(xy)\right]
\end{eqnarray*}
Now
\begin{eqnarray*}
E_{x,y}[\chi_S(x)\chi_T(y)\chi_U(xy)]& = & E_{x,y}\left[\prod_{i\in
S} x_i \prod_{j\in T} y_j \prod_{j\in U}x_ky_k\right] \\
& = & E_{x,y}\left[ \prod_{i\in S\Delta T}x_i \prod_{j\in T\Delta
U}y_j\right]\\
& = & E_x\left[\prod_{i\in S\Delta T}x_i\right]E_y\left[\prod_{i\in T\Delta U}y_i\right]
\end{eqnarray*}
And this will be non-zero only if $S\Delta T = T\Delta U = \phi
\implies S=T=U$. Hence
\begin{eqnarray*}
E_{x,y}[f(x)f(y)f(xy)] &= &\sum_S f_S^3\\
& \leq & \parn{\max_S f_S}\parn{ \sum_S f_S^2}\\
& = & \max_S f_S
\end{eqnarray*}
Also,
\begin{eqnarray*}
f_S &= &\innerp{f,\chi_S}\\
& = & \frac{1}{2^n}\sum_x f(x)\chi_S(x)\\
& = & \frac{1}{2^n}\parn{\sum_{f(x)=\chi_S(x)} 1 - \sum_{f(x)\neq
\chi_S(x)} 1}\\
& = & 1 - 2\Pr_x[f(x) \neq \chi_S(x)]
\end{eqnarray*}
Hence,
\begin{eqnarray*}
E_{x,y}[f(x)f(y)f(xy)] & \leq & \max_S f_S\\
& = & 1 - 2\min_S\Pr_x[f(x)\neq \chi_S(x)]\\
& = & 1 - 2\min d(f,\chi_S) \\
& = & 1 - 2\delta
\end{eqnarray*}
Hence
$$
\Pr[\text{BLR rejects}] = E_{x,y}\left[\frac{1 - f(x)f(y)f(xy)}{2}\right]
\geq \delta
$$
\end{proof}
\newpage
\lecture{ $4$}{V. Arvind}{Bireswar Das }{Ramprasad Saptharishi}
\section{Overview}
Last time we saw that the existence of a constant query assignment
tester completed the alphabet reduction process. This class we shall
construct a constant query assignment tester, and complete the proof
of the PCP theorem.
\section{A constant query assignment tester}
Given a circuit $\Phi$ as input, we need to output a set of
constraints with the properties that preserve gap. The first step that
we would be doing is arithmetize circuits.
\subsection{Arithmetizing Circuit-Sat}
Introduce variables for every input bit and also for every gate.
Let $x,y$ be the input wires and $z$ the output wire for some
gates. Add the following constraints for that gate:
\begin{itemize}
\item {\bf AND:} $xy - z=0$
\item {\bf OR:} $x+y-xy-z =0$
\item {\bf NOT:} $x + z = 1$
\end{itemize}
where all the operations are done over $\F_2$.
And to check if the output of the circuit is $1$, if $z$ is the
variable of output gate, we have add the constraint $z-1=0$.
We would now have one variable for every gate, apart from the
inputs. Let us refer to the set of equations as $\{P_1, \cdots,
P_m\}$. \\
Hence we now have a set of quadratic constraints to be checked to
solve circuit satisfiability.
\subsection{Testing Quadratic Systems}
Given an assignment $a\in \{0,1\}^N$ for the set of quadratic
equations, one could naively check by plugging in $a$ into every
constraint and check. But for this we would need to know the entire
assignment, we are looking for a constant number of queries to test
the system.
Hence instead of checking if $P_i(a)=0$ for every $i$, we shall look
at a random linear combination of them and check if the following is
zero:
$$
P_{\bar{r}}(a)\sum_{i=1}^m r_iP_i(a)=0
$$
Clearly, if each of the $P_i(a)=0$, then the linear combination would
be zero. And even otherwise, we have the following easy claim for the
soundness of the test.
\begin{claim}If $P_i(a)\neq 0$ for some $i$, then
$$
\Pr_{\bar{r}}\left[\sum r_iP_i(a)\right]=0
$$
\end{claim}
\noindent
By collecting all linear and quadratic terms separately,
$$
P_{\bar{r}}(a) = s_0 + \sum_{i=1}^N s_ia_i + \sum_{1\leq i,j\leq N}t_{ij}a_ia_j
$$
\begin{definition}
Given an assignment $a\in \{0,1\}^N$, define the following functions.
\begin{itemize}
\item $L(s) = \sum a_is_i$
\item $Q(t) = \sum a_ia_jt_{ij}$
\end{itemize}
\end{definition}
Hence our test amounts to checking if $P_{\bar{r}}(a) = s_0 + L(s) +
Q(t) = 0$. Recall the Hadamard encoding of a string $x$.
\begin{definition}
For a vector $x= \{x_1, \cdots, x_r\}$ over a field $\F$, the Hadamard
encoding of $x$, denoted by $Had(x)$ is given by:
$$
Had(x)(s)=\sum_{i=1}^{r} s_ix_i
$$
\end{definition}
The Hadamard code is the longest possible linear code that does not
have any repeated symbols as it contains all possible linear
combinations of $x$. \\
And the function $Q$ defined above is the {\em Quadratic Function}
encoding of the assignment $a$.
\begin{definition}
Given a vector $x = \{x_1, \cdots, x_r\}$ in a field $\F$, the
quadratic function encoding of $x$, denoted by $QF(x)$ is given by:
$$
QF(x)(t) = \sum_{1\leq i,j\leq r} x_i x_j t_{ij}
$$
\end{definition}
Note that the quadratic function encoding of $x$ is just the hadamard
encoding of the vector $x\otimes x$. \\
The assignment tester will now be described as a Prover-Verifier
protocol, since we are applying the assignment tester only on the
edges (which are of constant size) in our graph we are not worried
about the running time of the assignment tester.
Given a circuit, the verifier picks the random vector $\bar{r}$ and
based on that the prover provides the satisfying assignment (if any),
the table for $L$ and the table for $Q$ for the satisfying assignment.
Now with just two queries (one for $L$ and another for $Q$) the
verifier can check if $P_{\bar{r}}(a)=0$. But there is no guarantee
that the tables that the prover provided was correct, we need some way
to reject malicious provers.
The verifier needs to check for the following:
\begin{enumerate}
\item $L$ is a linear function, the hadamard encoding of some $c\in
\F_2^N$, and $Q$ is a liner function on $\F_2^n$, the hadamard
encoding of $C = \parn{C_{ij}}_{1\leq i,j\leq N}$.
\item $Q$ and $L$ are tables for the same assignment $c$, that is,
$C_{ij} = c_ic_j$. (this means that $Q$ is a quadratic function
encoding, not just a hadamard encoding of a vector)
\item The assignment that both the tables are referring to is indeed
the assignment to the set of quadratic constraints.
\end{enumerate}
The BLR test would check conditions $1$ with few queries (with high
probability). As for the other conditions, we would need some way of
finding the actual value of $L$ and $Q$ though the tables could be
slightly distorted; we need a way to self-correct.
\subsubsection*{The Self-Correct Algorithm: $SC(f,x)$}
\begin{itemize}
\item Pick $y$ at random
\item Output $f(x\oplus y) \oplus f(y)$
\end{itemize}
\begin{lemma}
If $f$ is $\delta$-close to a linear function $L$ for some
$\delta<\frac{1}{4}$, then for any $x\in \{0,1\}^n$ the algorithm
$SC(f,x)$ computes $L(x)$ with probability atleast $1 - 2\delta$.
\end{lemma}
\begin{proof}
Since $y$ and $x\oplus y$ are distributed uniformly at random,
\begin{eqnarray*}
\Pr_y[f(y)\neq L(y)] & \leq & \delta\\
\Pr_y[f(x\oplus y)\neq L(x\oplus y)] & \leq & \delta\\
\therefore \Pr_y[SC(f, x) = L(x)] & \geq & 1 - 2\delta
\end{eqnarray*}
\end{proof}
\noindent
Now for condition $2$, pick random $s,s' \in \{0,1\}^N$ and the
following must be true.
\begin{eqnarray*}
L(s)L(s') & = &\parn{\sum a_is_i}\parn{a_js'_j}\\
& = & \sum a_i a_js_is'_j\\
& = & Q(s\oplus s')
\end{eqnarray*}
And this can be checked by the self-correction procedure. \\
\noindent
And finally for condition $3$, to check if $a$ was the actual
assignment, we need to check if the coefficient of $s_i$ is $a_i$. And
hence we can randomly pick and $i$ and check if $SC(L,e_i) = a_i$. We
shall now put the assignment tester together and then formally prove
the completeness and soundness.
\subsection{The Final Assignment Tester}
\subsubsection*{Input}
A boolean circuit over variables $X$ and gates $Y$ such that $|X| +
|Y| = N$.
\subsubsection*{Initialization}
Arithmetize the circuit to get a set $\mathcal{P} = \{P_1, \cdots,
P_r\}$ of quadratic constraints over the variables $A = \{z_1, \cdots,
z_n\}$. Let $\{z_1, \cdots, z_{|X|}\}$ correspond to the variables of
$X$ and the rest for the gates $Y$.
\subsubsection*{The Proof Provided}
\begin{itemize}
\item The assignment $a =\parn{a_1, \cdots, a_N}\in \{0,1\}^N$ for the
variables $A$
\item A table $L$
\item A table $Q$
\end{itemize}
\subsubsection*{Verification}
\noindent
Step $1$:
\begin{itemize}
\item Run BLR on $L$
\item Run BLR on $Q$
\end{itemize}
\noindent
Step $2$: Pick $s,s'$ at random and check if the following holds:
$$
SC(L,s)SC(L,s') = SC(Q,s\otimes s')
$$
\noindent
Step $3$: Pick a random vector $\bar{r}$ and compute the coefficients
$s_i$ and $t_{ij}$ such that
$$
P_{\bar{r}}(a) = s_0 + \sum_{i=1}^N s_ia_i + \sum_{1\leq i,j\leq N} t_{ij}a_ia_j
$$
and check if
$$
s_0 + SC(L,S) + SC(Q,T) = 0
$$
\noindent
Step $4$:
Pick a random $i\in \{1,2,\cdots, |X|\}$. Check if
$$
SC(L,e_i) = a_i
$$
\subsection{Proof of Correctness}
Completeness of the entire test is clear, an honest prover will
convince the verifier with probability $1$ since he would pass every
step of the verifier's procedure. \\
Firstly, if $L$ or $Q$ is $\delta$-far from a linear function, then by
the soundness of the BLR test we know that step $1$ would reject with
probability $\geq \delta$. For step $2$, we would be needing this
simple lemma.
\begin{lemma}
Given a non-zero matrix (atleast $1$ non-zero entry) $M$, for a random
choice of vectors $s,s'$,
$$
\Pr_{s,s'}[s^TMs' = 0 ]\leq \frac{3}{4}
$$
\end{lemma}
\begin{proof}
Let $M_{ij}$ be the non-zero entry, note that
$$
s^TMs' + (s + e_i)^TMs' + s^TM(e_j + s') + (s + e_i)^TM(s' + e_j) =
e_i^TMe_j = M_{ij}
$$
And hence this is non-zero, atleast one of the the above has to be
non-zero. And since they are all identically distributed, the lemma follows.
\end{proof}
\begin{lemma}
If $L$ is $\delta$-close to $Had(c)$ and $Q$ is
$\delta$-close to $Had(C)$ such that $C_{ij}\neq c_ic_j$ for some
$i,j$, then step $2$ rejects with probability atleast $\frac{1}{4} - 6\delta$
\end{lemma}
\begin{proof}
Since $L$ is $\delta$-close to $Had(c)$, by our earlier lemma we know
that with prob atleast $1 - 2\delta$, $SC(L,s) = L(s) = s^Tc$, and
similarly for $Q$.
And thus with probability atleast $1 - 6\delta$, the equality being
tested in step $2$ is
\begin{eqnarray*}
s^Tcc^Ts' &= & s^TCs'\\
\implies s^T(cc^T - C)s'& = &0
\end{eqnarray*}
And since $cc^T - C$ is a non-zero matrix by assumption, the earlier
lemma bounds this probability by $\frac{3}{4}$. And hence, the lemma
follows.
\end{proof}
\begin{lemma}
If $L$ is $\delta$-close to $Had(c)$ and $Q$ is $\delta$-close to
$QF(c)$ and if $P_j(c) \neq 0$ for some $j$, then step $3$ rejects
with probability atleast $\frac{1}{2}-4\delta$
\end{lemma}
\begin{proof}
With the accuracy of the self-correct routine, with probability
atleast $1 - 4\delta$,
$$
P_{\bar{r}}(a) = s_0 + \sum_{i=1}^N s_i a_i + \sum_{1\leq i,j \leq N}
t_{ij}a_ia_j
$$
is equivalent to the check in step $3$:
$$
s_0 + SC(L,S) + SC(Q,T)
$$
And from our earlier lemma, we know that if $P_i(c)\neq 0$ for some
$j$, then with probability $\frac{1}{2}$ this above evalutes to
$0$. Hence with probability atleast $1 - 2\delta - \frac{1}{2}$
$$
s_0 + SC(L,S) + SC(Q,T) \neq 0
$$
and thus step $3$ would reject.
\end{proof}
\begin{theorem}
For a suitable bound on $\delta$, if an assignment $a$ to our
initial circuit $\Phi$ was $\delta$-far from the closest satisfying
assignment to the circuit, then the test rejects wiht probability
atleast $\frac{\delta}{8}$ irrespective of the contents of the
tables.
\end{theorem}
\begin{proof}
Firstly, if $L$ or $Q$ were $\delta$-far from the nearest Hamming
codeword, then step $1$ rejects it with probability atleast
$\delta$. And if they do not refer to the same assignment, then
step $2$ would catch that with probability atleast $\frac{1}{4} -
6\delta$.And if $a$ is not a satisfying assignment to $\mathcal{P}$,
then with probability atleast $\frac{1}{2}-4\delta$ we catch that in
step $3$.
If the assignment $a_X$(the restriction to just the input variables)
was $\delta$-far from any satisfying assignment for the circuit
$\Phi$, and in particular $c_X$($c$ being the satisfying
assignment for $\mathcal{P}$). And with probability atleast $1 -
2\delta$, $SC(L,e_i) = c_i$. Since $a_X$ is $\delta$-far from $c_X$,
then with probability $\delta$, $a_i \neq c_i$ over the random
choice of $i$ in $\{1,2,\cdots, |X|\}$ and hence with probability
atleast $\delta(1 - 2\delta)$ the verifier rejects in step $4$. \\
The total accumulated error can be shown to be less than
$\frac{\delta}{8}$ for a suitable bound on $\delta$. \footnote{in class
we did each of the steps with probability $\frac{1}{4}$ and for
that $\delta < \frac{1}{28}$ was good enough}
\end{proof}
\section{The End Game}
All that's left to be done is to derandomize this protocol, and since
we don't care about any resource bounds, we can enumerate all possible
random strings and do this. We can then output the set of constraints,
such that each constraint depends on only a constant number of
variables ($6$, I think; the BLR takes $6$ queries, $24$ is definitely
an upper bound).
And hence for every edge in our old constraint graph, we now have
exponentially many constraints, but we can do this without and hastles
since it still only is a constant size increase in the size of $G$. \\
However, if we were to apply the $4$ steps on the entire original
graph, we would get an exponential sized proof. This was more or less
the proof of the earlier result that $NP\subseteq PCP(n^3, O(1))$. \\
Now we have a constant query assignment tester, and hence alphabet
reduction, and thus the PCP reduction required to prove Dinur's
theorem with suitable choice of the parameter $t$ to double the
gap. And that completes the proof of the PCP theorem. \qed
\section{Brief Sketch of the Proof}
\begin{enumerate}
\item Showing that the gap version of three colourability was
$NP$-hard implied the PCP theorem. Hence we wanted to amplify the
gap from $(1,1 - 1/m)$ to $(1,s)$ for some $s$.
\item The PCP Reduction was done in $4$ steps:
\item Degree reduction: We just spread every vertex of our graph
into a cycle, and put an expander on every cloud.
\item Expanderize: Super-imposed an expander over this graph.
\item Gap Amplification: We used ``lazy random walks'' to amplify
the gap. This on the other hand increased the alphabet size.
\item In order to reduce the alphabet size, we were on the lookout for
a $2$ query assignment tester. We then showed that any constant
query assignment tester can be used to construct a $2$-query
assignment tester. The idea was to put this assignment tester on
every edge, since edges were of constant size, running time of the
assignment tester wasn't crucial.
\item In order to get a constant query assignment tester, we
arithmetized circuits, to give is a set of quadratic constraints.
\item With the BLR tests and the self-correction procedure, we deviced
a Prover-Verifier protocol where the verifier, which on
derandomization gave us a constant query assignment tester.
\item The derandomized version is now used for every edge in our
constraint graph, thereby reduces the alphabet size back to constant
size with just a constant factor increase in the size and gap, which
can be compensated for in the ``Gap Amplification'' process with the
choice of $t$ in hand.
\item And thus we have a way of doubling the gap with just a constant
size increase in the graph size. This then allowed us to repeat this
for $O(\log n)$ steps to get the gap from $(1, 1 - 1/m)$ to $(1,s)$,
and thus proving Dinur's Theorem, and hence the PCP Theorem
\end{enumerate}
\end{document}