\documentclass[10pt]{article}
\usepackage{amsfonts}
\usepackage{fullpage}
%\usepackage{epsfig}
\begin{document}
\input{preamble.tex}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1ex plus 0.5ex minus 0.2ex}
\lecture{20}{April 22, 2009}{Madhu Sudan}{Kristian Brander}
\section{Introduction}
The purpose of todays lecture is to explore the landscape of PCPs. In particular three constructions of Dinur, Raz and H\aa stad will be surveyed.
\section{Recap from previous lectures}
\subsection{The PCP class}
A language $L$ is in $\textrm{PCP}_{c,s}(r,q)$ if there exists a verifier $V$ such that
\begin{itemize}
\item If $x \in L$ there exists a proof $\pi$, such that $V$ accepts with probability $c(n)$.
\item If $x \not\in L$ then for all proofs $\pi$, $V$ accepts with probability at most $s(n)$.
\end{itemize}
\subsection{Adaptive and non--adaptive verifiers}
One distinguishes between adaptive and non--adaptive verifiers. For adaptive verifier its $i$th query can depend on ``the past'' i.e. on the previous queries. For non--adaptive verifiers, the positions in the proof to be queried should be read simultaneously.
By definition adaptive verifiers are stronger than non--adaptive ones. An adaptive verifiers decision of which position to query next (given the past), may be represented as a decision tree, and therefore by querying all nodes at once, an adaptive verifier with $q$ queries can be converted into a non--adaptive verifier using $2^q$ queries.
Though less powerful, the non--adaptive verifiers have the advantage of being simpler to reason about and in fact the best known PCP constructions have non--adaptive verifiers. However the two types of verifiers really have different properties as the combination of the following results show. H\aa stad in \cite{DBLP:journals/jacm/Hastad01} and Guruswami, Lewin, Sudan and Trevisan in \cite{DBLP:conf/focs/GuruswamiLST98} shows that
\[\textrm{NP} \subseteq \textrm{PCP}_{1,0.51}\left[\mathcal{O}(\log n), 3\right],\]
which can be compared to a result of Trevisan and Zwick
\[\textrm{NAPCP}_{1,0.51}(\mathcal{O}(\log n, 3) \subseteq P.\]
Here $\textrm{NAPCP}_{c,s}(r,q)$ denotes the class of languages that has non--adaptive PCP verifiers.
\subsection{Generalized graph coloring}
Let $G$ with vertex set $V$ and edges $E \subseteq V^t$ where $t$ is an integer. Given $k$ colors and constraints $\left\{\pi_e : \{1,\ldots,k\}^t \rightarrow \{0,1\} \right\}_{e \in E}$, the gap--generalized hypergraph coloring problem $\textrm{GGHC}_{c,s}(t,k)$ is to find an assignment of colors $A : V \rightarrow \{1,\ldots,k\}$ satisfying the constraints. $\textrm{UNSAT}(G)$ is the minimal fraction of unsatisfied edges for any assignment of colors.
For a given graph $G$, one may try to separate the two cases $\textrm{UNSAT}(G) \leq 1-c$ and $\textrm{UNSAT}(G) \geq 1-s$, and this establishes a connection between hypergraph coloring and PCPs: To a proof one associates a hypergraph whose vertices are the bits of the proof and the hyperedges are queries. A proof can then be thought of as a coloring of the hypergraph, and the checks done by the verifier, as checking whether certain edge constraints $\pi_e$ are satisfied. One can prove that
\begin{eqnarray*}
\textrm{GGHC}_{c,s}(t,k) & \subseteq & \textrm{NAPCP}_{c,s}(\mathcal{O}(\log n), t\log k) \\
\textrm{NAPCP}_{c,s}(\log n,q) & \subseteq & \textrm{GGHC}_{c,s}(q, 2)
\end{eqnarray*}
Thus hypergraph coloring problems may be translated to PCPs and vice versa, with appropriate care in the choice of parameters.
\subsection{Hypergraph coloring and coloring of (ordinary) bipartite graphs}
Generalized hypergraph coloring can be reduced to coloring ordinary (bipartite) graphs, at the expense of having to deal with more colors, more specifically
\[\textrm{GGHC}_{1,1-\varepsilon}(t,k) \leq \textrm{GeneralizedGraphColoring}_{1,1-\frac{\varepsilon}{t}}(k^t).\]
This is done as follows: For a $t$--regular hypergraph $G = (V,E)$ with constraints $\pi_e$, construct the ordinary bipartite graph $G'$ as follows: Let the left vertex set of $G'$ be $V$ and the right vertex set be $E$ and connect a pair of vertices $(v,e)$ in $G'$ if $v \in e$ in the original graph $G$. The constraint on $G'$ are now on $k^t$ colors and are saying that the coloring of $G'$ should be ``consistent'' with the constraints on $G$. More specifically, an assignment of colors will satisfy the constraint $\pi'_{(v,e)}$ for an edge $(v=v_i,e=(v_1,\ldots,v_t))$ if the color of $v_i$ and the $i$--th component of the color of $e$ agree, and if the coloring of $e$ satisfies the constraint $\pi_e$ from the original graph. A coloring of the hypergraph implies a coloring of the associated bipartite graph, and so the transformation is consistency preserving. Checking the claim on the soundness is left as an exersice. The transformation first appeared in [Fortnow, Rompel and Sipser].
\section{Dinur's construction}
The main ingredients in Dinur's proof of the PCP theorem \cite{Dinur05} are the following two lemmas
\begin{lemma}[Amplification Lemma]
$\forall C \exists K, \varepsilon$ such that there is a linear time transformation from
\[\textrm{GeneralizedGraphColoring}(k) \rightarrow \textrm{GeneralizedGraphColoring}(K),\]
mapping $G$ to $\tilde{G}$ such that
\begin{itemize}
\item $\textrm{UNSAT}(G) = 0$ implies $\textrm{UNSAT}(\tilde{G}) = 0$.
\item $\min\{\varepsilon, C\cdot \textrm{UNSAT}(G)\} \leq \textrm{UNSAT}(\tilde{G})$
\end{itemize}
\end{lemma}
For comprehensibility, one may ignore the appearance of $\varepsilon$ in the above lemma, and simply read it as a statement saying that \emph{there is a linear time transformation which amplifies gaps}.
\begin{lemma}[$K$--reduction Lemma]
$\exists\delta\forall K$ there is a transformation from $\textrm{GeneralizedGraphColoring}(K)$ to $\textrm{GeneralizedGraphColoring}(k)$ mapping $G$ to $\tilde{G}$, such that
\[\delta\cdot\textrm{UNSAT}(G) \leq \textrm{UNSAT}(\tilde{G}).\]
\end{lemma}
With these two lemmas at hand, Dinur's proof consists of combining the parameters (and quantifiers) in the above statements.
There exists ``stronger'' versions of the PCP theorem, where more attention is paid to the ingoing constant. The current state of the art is [Moshkovitz, Raz], which shows that
\[\textrm{SAT} \in \textrm{PCP}_{1-\varepsilon,1/2}((1+o(1))\log_2 n, 3).\]
We will not go into the details of this result, but instead survey other constructions by Raz and H\aa stad.
\section{Raz's construction}
Raz's PCP theorem may be stated as a transformation between two instances of the generalized graph coloring problem for bipartite graphs.
\begin{theorem}
$\forall s,k \exists \bar{s}$, such that $\forall t$ it holds that
\[\textrm{BipartiteGeneralizedGraphColoring}_{c,s}(k) \leq \textrm{BipartiteGeneralizedGraphColoring}_{c^t,\bar{s}^t}(k^t).\]
Furthermore, if $s < 1$ then $\bar{s} < 1$.
\end{theorem}
Let $G = (V = L \cup R,E)$ be a bipartite graph, where $L$ and $R$ denotes the left and right vertex set of $G$ respectively. The proof of the theorem relies on repeating the graph ``$t$--fold'', by constructing a new bipartite graph $\tilde{G}$ with left vertex set $L^t$ and right vertex set $R^t$ and connecting two nodes $(u_1,\ldots,u_t) \in L^t$ to $(v_1,\ldots,v_t) \in R^t$ if $u_i$ and $v_i$ are connected in $G$, for all $i$. The edge constraints in the new graph are conjunctions of the edge constraints from $G$:
\[\pi_{((u_1,\ldots,u_t),(v_1,\ldots,v_t))} = \bigwedge_i \pi_{(u_i,v_i)}.\]
This is what gives the exponent $t$ on the consistency parameter in the theorem. The hard part is to bound the soundness, details of the analysis can be found in a survey by Holstein.
By the way we translated PCPs into graph coloring problems, where the verifier probes a (small) number of random edges, decreasing soundness is like increasing $\textrm{UNSAT}$. If $s < 1$, increasing $t$ makes the soundness go down exponentially, and therefore one may think of Raz's result as a parallel to Dinur's gap amplification theorem. The main differences are:
\begin{itemize}
\item In Dinur's construction the absolute constant $\varepsilon$ bounds how $\textrm{UNSAT}$ increases with repeated transformations. In contrast, with Raz's construction the soundness can be made arbitrarily close to $0$.
\item In Dinur's transformation the size of the resulting graph is $\mathcal{O}(n)$, whereas for Raz's construction it grows exponentially with $t$.
\end{itemize}
Therefore Dinur's gap amplification and Raz's transformation, are not equivalent, but are similar, with different tradeoffs between soundness and size.
\section{H\aa stad's construction}
H\aa stad's PCP theorem can again be viewed as a result on generalized graph coloring.
\begin{theorem}
For all $\delta > 0$ there exists $\varepsilon > 0$ such that
\[\textrm{GeneralizedGraphColoring}_{1,\delta}(K) \leq \textrm{GGHC}_{1-\varepsilon,1/2}(3,2).\]
\end{theorem}
The result is a translation from coloring with many ($K$) colors to coloring with only 2 colors and thus it may be viewed as a parallel to Dinur's $K$--reduction lemma. The theorem implies that
\[\textrm{NP} \subseteq \textrm{PCP}_{1-\varepsilon,1/2+\varepsilon}(\mathcal{O}(\log n), 3).\]
The proof of the theorem consists of giving a reduction from bipartite graph coloring with $K$ colors (and so--called projective constraints) to colorings of $3$--regular hypergraphs using only $2$ colors. A constraint is said to be projective if $\pi_(u,v)$ only depends on $v$, i.e. if it is \emph{function} of this vertex.
Let $f : \{1,\ldots,K\} \rightarrow \{-1,1\}$ be a function (here $\{-1,1\}$ should be thought of as a bit, and this representation is chosen to facilitate the analysis using Fourier analysis). The value of the function $-f$ at any point is just minus the value of $f$ at the same point. Therefore $f$ and $-f$ may be considered equivalent, and modulo this ``equivalence relation'' there are $2^{K-1}$ functions from $\{1,\ldots,K\}$ to $\{-1,1\}$.
From $G$ a new bipartite graph $G'$ is constructed by expanding each vertex $v$ (both on the left and the right side) to a cloud of $2^{K-1}$ vertices, indexed by $(u,f)$ where $f$ is a function of the above type. One should think of each cloud $U$ as a function table holding values $U[f] = f(\textrm{Color}(u))$, except at the positions with errors. The verifier will then be checking relations between the functions given by these tables.
The verifier will be asking three questions of the form ``what is the value of $f(\textrm{Color}(u))$?''. It will ask three such questions on an ``edge'' between one vertex on the left vertex set and two vertices on the right vertex set. The edge will be chosen randomly, by first taking $(u,f)$ randomly from the left vertex set, then $(v,g)$ randomly from the right vertex set and then finally $(v, f \circ \pi_e)$, again from the right set, where $\pi_e$ is the edge constraint. If the chosen vertices are error--free it will hold that
\[\textrm{Color}(v,g)\cdot \textrm{Color}(u,f) = \textrm{Color}(v, (f \circ \pi_e) \cdot g),\]
and the verifier could use this relation as its ``check'' on the edge. However, these checks are not quite strong enough for the verifier. Instead checks of the form
\[\textrm{Color}(v,g)\cdot \textrm{Color}(u,f) = \textrm{Color}(v, (f \circ \pi_e) \cdot g\cdot \eta),\]
are used, where $\eta : \{1,\ldots,K\} \rightarrow \{-1,1\}$ is some noisy function such that $\eta(i) = 1$ with high probability $1-\varepsilon$ and $\eta(i) = -1$ with probability $\varepsilon$. This scheme suffices to give the result stated in the theorem. The analysis of the consistency and soundness parameters relies on Fourier analysis of boolean functions.
\bibliographystyle{alpha}
\bibliography{lect20}
\end{document}