\documentclass[10pt,letterpaper]{article}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[letterpaper, dvips]{geometry}

%\usepackage{epsfig}

\newcommand{\valid}{\operatorname{valid}}
\newcommand{\unsat}{\operatorname{unsat}}

\begin{document}
\input{preamble.tex}

\lecture{20}{April 25, 2007}{Madhu Sudan}{Alex Schwendner}


\section{Generalized $r$-Graph $k$-coloring}
Our goal for this lecture is to prove the PCP Theorem using Dinur's
proof by Gap Amplification~\cite{dinur}. For this, we'll be using our
second view of PCPs, namely Generalized Graph Coloring.

For a given triple $(k,r,\epsilon)$, the Generalized $r$-Graph
$k$-coloring problem consists of a graph $(V,E)$ along with a notion
of which colorings are valid for each hyper-edge:

\begin{align*}
G = (V, E &, \valid : E \times [k]^r \longrightarrow \left\{0,1\right\}) \\
E & \subseteq \underbrace{V \times V \times \cdots \times V}_{r\text{-times}}
\end{align*}

We define a \emph{$k$-coloring} to be an assignment of one of $k$
colors to each vertex: $\chi : V \longrightarrow
\left\{1,\ldots,k\right\}$. For a coloring $\chi$, we call an edge
$e=(v_1,\ldots,v_r)$ \emph{satisfied} if $\valid(e, \chi(v_1), \ldots,
\chi(v_r)) = 1$. The graph $G$ is then called \emph{$k$-colorable} if
there exists a coloring $\chi$ such that all edges are satisfied.

We consider the promise problem for which we want to accept if $G$ is
$k$-colorable, and reject if at least an $\epsilon$ fraction of the
edges are unsatisfied in any coloring of $G$. If we define
\begin{align*}
\unsat_\chi(G) &= \frac{\lvert \left\{e \in E \; \vert \; e \text{ not satisfied by } \chi\right\}}{\lvert E \rvert} \\
\unsat(G) &= \min_\chi \left\{\unsat_\chi(G)\right\}
\end{align*}
then  we can specify that we wish to reject $G$ if $\unsat(G) \geq \epsilon$.

\section{Reductions}
\subsection{Definition}
We define a reduction $(k,r,\epsilon) \longrightarrow
(k',r',\epsilon')$ to be a linear-time reduction mapping an $r$-graph
$G$ to an $r'$-graph $G'$ such that if $G$ is $k$-colorable, then $G'$
is $k'$-colorable, and if $\unsat(G) \geq \epsilon$ then $\unsat{G'}
\geq \epsilon'$:
\begin{eqnarray*}
r\text{-graph } G & \longrightarrow & r'\text{-graph } G' \\
G \; k\text{-colorable} & \Longrightarrow & G' \; k'\text{-colorable} \\
\unsat(G) \geq \epsilon & \Longrightarrow & \unsat(G') \geq \epsilon'
\end{eqnarray*}

\subsection{Classical Reductions} \label{classical-reductions}
Here are some easy classical (or neo-classical) reductions:
\begin{enumerate}
\item \label{classical-start} $(k,r,\epsilon) \longrightarrow \left(2, r \log k,
    \epsilon\right)$ --- Here, we replace each vertex with $\log k$
  vertices with binary colors that encode the previous $(\log k)$-bit
  coloring. Then, we expand each edge to cover all $r \log k$ vertices
  used to represent the former $r$ vertices.
\item \label{frs} $(k,r,\epsilon) \longrightarrow \left(k^r, 2, \dfrac{\epsilon}{r}\right)$ --- This was in Lecture 18.
\item $(k,2,\epsilon) \longrightarrow \left(3, 2, \dfrac{\epsilon}{f(k)}\right)$ ---~\cite{PY}
\item \label{classical-end} $(2,r,\epsilon) \longrightarrow \left(2, 3, \dfrac{\epsilon}{r}\right)$ --- By Cook
\item \label{neoclassical} $(k,r,\epsilon) \longrightarrow (k, c\cdot r, \underbrace{\approx \epsilon \cdot c}_{= 1 - (1 - \epsilon)^c})$ --- based on expander walks
\end{enumerate}
However, these don't help us prove the PCP Theorem. In reductions
\ref{classical-start} through \ref{classical-end}, $\epsilon$ only
goes down, but we need to make $\epsilon$ equal to $1/2$ to prove the
PCP theorem. In reduction \ref{neoclassical}, $\epsilon$ does get
bigger, but the ratio $\dfrac{r \cdot \log k}{\epsilon}$ still gets
bigger, not smaller. This ratio is approximately what we want to have
be small, but none of these reductions decrease it.

\section{Dinur}
The reductions in \ref{classical-reductions} aren't enough to prove the PCP Theorem. Dinur's proof, however, relies on two key lemmas.

{\lemma \label{lem1} (Gap Amplification) $\forall \, c,k \;\; \exists \,K$ such that $\forall \,\epsilon$, \[(k,2,\epsilon) \longrightarrow (K,2, c\cdot \epsilon).\]}

{\lemma
  \label{lem2} $\exists \,\delta$ such that $\forall \, K$, \[(K,2,\epsilon) \longrightarrow (2,4,\epsilon\delta).\]}

Note that the $\delta$ in Lemma \ref{lem2} is fixed. Thus, fix
$c=8/\delta$. Now, for $k=16$, let $K$ be as implied by Lemma
\ref{lem1}. We can combine Lemma \ref{lem1} and Lemma \ref{lem2} with
Reduction \ref{frs} from Section \ref{classical-reductions} to prove
{\lemma
  \label{lem3} $(16,2,\epsilon) \longrightarrow (16,2,2\epsilon)$}:
\begin{align*}
(16,2,\epsilon) & \xrightarrow{\text{Lemma \ref{lem1}}} (K, 2, \epsilon c) \\
& \xrightarrow{\text{Lemma \ref{lem2}}} (2,4,8\epsilon) \\
& \xrightarrow{\text{Reduction \ref{frs}}} (16,2,2\epsilon)
\end{align*}

What Lemma \ref{lem3} lets us do is increase the size of the gap from
$\epsilon$ to $2\epsilon$ with a linear reduction.

We claim that our work in Lecture 19 can be seen to imply Lemma
\ref{lem2}. Informally, a PCP is more than just a proof, but is a
commitment to a specific proof. We can adapt our with in showing how
to check a PCP to check a graph coloring.

Let $l = \log k$. We split each vertex $v$ into a cloud of $k$
vertices.  For each of these vertices $i$, we choose a linear function
$L_i$ and let the color of $i$ be the bit $L_i(\chi(v))$ where
$\chi(v)$ is considered as a $(\log k)$-bit vector. The constraints
that we checked of the form $\Pi[Q_1] + \Pi[Q_2] = \Pi[Q_1 + Q_2]$ for
a valid PCP get modeled as 3-edges.

Next, Dinur's proof of Lemma \ref{lem1}. We first sketch a weak
reduction with expander walks as in Reduction \ref{neoclassical}.
There, we take a random walk on $G$, and take the conjunction of the
constraints on the edges we traverse. If $G$ is an expander then this
will amplify the error gap ($\epsilon$). However, with this, $r$ will
increase but we need $r$ to stay the same while $k$ increases to $K$.

Instead, in Dinur's construction, we start by fixing a constant $t$
and then letting $B_v = B_v^t = \left\{u \; \vert \; \delta(u,v) \leq
  t\right\}$ where $\delta(u,v)$ is the length of the shortest path
between $u$ and $v$ in $G$. We now define our reduction
\begin{align*}
G&=(V,E,\valid) \\
&\downarrow \\
G' = G_t' &= (V', E', \valid ')
\end{align*}
where
\begin{align*}
  V' &= V \\
  E' &= \left\{(u,v) \;\vert\; \exists w_1\cdots w_l \text{ s.t. }
    w_1=u, w_l=v, (w_i, w_{i+1}) \in E, \frac{t}{2} \leq l \leq
    t\right\} \text{ as a multiset} \\
  \chi' &\colon u \longmapsto \left\{\chi_u \colon B_u \longrightarrow \left\{1,\ldots,k\right\}\right\}.
\end{align*}
That is, each new edge $(u,v)$ is the collection of paths from $u$ to
$v$, and each new coloring of $u$ $\chi'(u)$ is a function specifying
the old coloring on $B_u$, the neighborhood of $u$. We then require
that these colorings can be stitched together to form a valid coloring
of the entire graph.

Specifically, for some $u$ and $v$ connected by an edge $(u,v) \in
E'$, $\valid'(\chi_u, \chi_v)=1$ if
\begin{enumerate}
\item $\forall \; w \in B_u \cap B_v$, $\chi_u(w) = \chi_v(w)$
\item $\forall e=(w_1, w_2) \in E$ with $w_1, w_2 \in B_u \cap B_v$,
  $\valid(e, \chi_u(w_1), \chi_v(w_2)) = 1$.
\end{enumerate}

This construction produces a graph with $r$ still equal to $2$.
However, our new colors imply much more about the state of the graph
and thus checking each edge gives more information. By choosing a
large enough value for $t$, we can then get any desired increase in
strictness $\epsilon$. The number of colors increases to some $K$.
This proves Lemma \ref{lem1}.


\bibliographystyle{alpha}
\bibliography{lect20}


\end{document}