\documentclass[10pt]{article}
\usepackage{amsfonts,amssymb}
\usepackage{fullpage}
\usepackage{psfrag,epsfig}
\begin{document}
\input{preamble.tex}
\lecture{18}{Apr 13, 2009}{Madhu Sudan}{Jinwoo Shin}
In this lecture, we will discuss about $PCP$ ({\em probabilistically checkable proof}). We first overview the history followed by the formal definition of $PCP$ and then study its connection to inapproximability results.
\section{History of $PCP$}
Interactive proofs were first independently investigated by Goldwasser-Micali-Rackoff and Babai.
Goldwasser-Micali-Wigderson were focused on the cryptographic implications of this technique;
they are interested in {\em zero-knowledge} proofs, which prove that one has a solution of a hard problem without
revealing the solution itself. Their approach is based on the existence of one-way functions.
Another development on this line was made by BenOr-Goldwasser-Kilian-Wigderson who
introduced several provers. $2IP$ has two provers who may have agreed on their strategies before
the interactive proof starts. However, during the interactive proof, no information-exchange is allowed
between two provers. The verifier can them questions in any order.
The authors showed that with 2 provers, zero-knowledge proofs are possible without assuming
the existence of one-way functions.
Clearly, $2IP$ is at least as powerful as $IP$ since the verifier could just ignore the second prover.
Furthermore, one can define $3IP$, $4IP$, $\dots,MIP$ and naturally ask whether those classes
get progressively more powerful. It turns out that the answer is no by Fortnow-Rompel-Sipser.
They proved that $2IP=3IP=\dots=MIP=OIP$, where $OIP$ is called {\em oracle interactive proof}.
$OIP$ is an interactive proof system with a memoryless oracle;
all answers are committed to the oracle before the interactive proof starts and
the oracle just answer them (without considering the previous query-history) when the verifier query them.
Now we consider the difference between $OIP$
and $NEXPTIME$. They both have an input $x$ of $n$ bits and a proof(certificate) $\pi$ of length $2^{n^c}$ for some
constant $c$. The difference relies on the verifier $V$. If $L\in NEXPTIME$,
there exists a deterministic-exptime $V$ such that
\begin{itemize}
\item If $x\in L$, then there exists a $\pi$ such that $V(x,\pi)$ accepts,
\item If $x\notin L$, then $\forall\,\pi$, $V(x,\pi)$ rejects.
\end{itemize}
Similarly, if $L\in OIP$,
there exists a randomized-polytime $V$ such that
\begin{itemize}
\item If $x\in L$, then there exists a $\pi$ such that $V(x,\pi)$ accepts with high probability,
\item If $x\notin L$, then $\forall\,\pi$, $V(x,\pi)$ accepts with low probability.
\end{itemize}
Hence the relation $OIP\subseteq NEXPTIME$ is obvious since one can build the verifier for $NEXPTIME$
by simulating all random coins of $V$ in $OIP$.
More interestingly, Babai-Fortnow-Lund showed the other direction $OIP\supseteq NEXPTIME$.
Using this relation $MIP=OIP=NEXPTIME$, Feige-Goldwasser-Lovasz-Safra-Szegedy proved
that the maximum clique-size of a graph is hard to approximate and
later Arora-Lund-Motwani-Sudan-Szegedy found the more general class of optimization problems,
called {\em MAX-SNP} problems, which are hard to approximate.
Note that in the description of $OIP$, $V$ checks only poly-many places of
exponentially large-sized proof $\pi$. One can generalized this concept,
and consider an oracle interactive proof system with
$\gamma(n)$ random bits used by the verifier $V$ and
$q(n)$ bits queried from the oracle by $V$. Here $n$ is the number of bits in the input $x$.
Arora-Safra first introduce this notation as
the probabilistically checkable proof class $PCP[\gamma(n),q(n)]$, which can be defined formally as follows.
\begin{definition}
The language $L$ is in $PCP_{c,s}[\gamma(n),q(n)]$ if there exists a $PCP$-verifier $V$, which uses
$\gamma(n)$ random bits and queries $q(n)$ bits from the oracle, such that
\begin{itemize}
\item If $x\in L$, then there exists a $\pi$ such that $V(x,\pi)$ accepts with probability $\geq c$,
\item If $x\notin L$, then $\forall\,\pi$, $V(x,\pi)$ accepts with probability $\leq s$.
\end{itemize}
\end{definition}
Otherwise we mention $c$ and $s$ in the above definition,
we implicitly assume $c=1$ and $s<1-\varepsilon$ for $\varepsilon>0$.
Hence, in this notation, $NEXPTIME=OIP=PCP[poly(n),poly(n)]$.
Now, it is natural to ask what other complexity classes we can get by varying $\gamma$ and $q$.
On the line of this question, Babai-Fortnow-Levin-Szegedy proves that
$NP\subseteq PCP[poly(\log n),poly(\log n)].$
Arora-Safra improved this by showing that $NP\subseteq PCP[O(\log n),O(\sqrt{\log n})]$,
and finally Arora-Lund-Motwani-Sudan-Szegedy (and later Dinur)
proved that $$NP\subseteq PCP[O(\log n),O(1)],$$ which is called $PCP$-Theorem.
This was improved even further by Hastad and Moshkovitz-Raz who gave proofs of $NP\subseteq PCP_{c,s}[O(\log n),3]$
and $NP\subseteq PCP_{c,s}\left[\left(1+o(1)\right)\log n,3\right]$ respectively,
where $c=1$ and $s= 1/2+o(1)$. In this lecture, we will study the proof of $PCP$-Theorem
presented by Dinur.
\section{Inapproximability of MAX-3SAT}
Before we look at the proof of PCP-Theorem, we present its connection to the inapproximability of MAX-3SAT problem.
First we define MAX-3SAT problem. For given $m$ clauses on $n$ Boolean variables with each clause of length at most 3,
the goal of this problem can be stated as follows depending on which types of problems we consider.
\begin{itemize}
\item[$\circ$] (Search) Find an assignment which satisfies the maximum number of clauses.
\item[$\circ$] (Optimization) Find the maximum number $OPT$ in above Search problem.
\item[$\circ$] (Decision) Decide whether $OPT\geq t$ for a given $t$.
\end{itemize}
Similarly, the approximation versions of these goals can be stated for a given approximation-ratio $\alpha\geq1$.
\begin{itemize}
\item[$\circ$] (Search) Find an assignment which satisfies more than $\frac{OPT}{\alpha}$ clauses.
\item[$\circ$] (Optimization) Find a number $x$ such that $\frac{OPT}{\alpha}\leq x\leq OPT$.
\item[$\circ$] (Decision) Decide whether $OPT\geq t$ or $OPT\leq \frac{t}{\alpha}$ for a given $t$.
\end{itemize}
We note that the search problem is the hardest and the decision problem is the easiest.
In 1976, Johnson gave an algorithm with $\alpha=2$ for this problem. (His algorithm is somewhat trivial by choosing a random assignment and its complement, but
he settles the concept of the approximation ratio.) Later in 1992, Yannakakis developed a highly nontrivial algorithm with $\alpha=\frac43$. The current best algorithm which was given by Zwick in 1998 has $\alpha=\frac87$. Using $PCP$-Theorem, Hastad in 1998 showed that this $\frac87$ is best one can achieve under assuming $P\neq NP$. Today, we will prove a weaker version that $\alpha<\frac{16}{15}$ cannot be achievable if $P\neq NP$.
To prove this, for any $NP$-complete language $L$, it is sufficient to construct a poly-time reduction $f$ such that
$f(x)=(\phi,t)$ and it satisfies the following:
\begin{itemize}
\item If $x\in L$, then $OPT(\phi)\geq t$,
\item If $x\notin L$, then $OPT(\phi)< \frac{15}{16}t$.
\end{itemize}
Here, $\phi$ is a 3SAT formula and $t$ is a positive integer.
\begin{figure}[htb]
\begin{center}
\begin{psfrags}
\psfrag{a}[t]{$\pi_{i_1}$}
\psfrag{b}[t]{$\pi_{i_2}$}
\psfrag{c}[t]{$\pi_{i_3}$}
\psfrag{d}[t]{$\pi_{i_4}$}
\psfrag{e}[t]{$\pi_{i_5}$}
\psfrag{f}[t]{$\pi_{i_6}$}
\psfrag{g}[t]{$\pi_{i_7}$}
\psfrag{h}[t]{\small Re}
\psfrag{i}[t]{\small Ac}
\psfrag{j}[t]{0}
\psfrag{k}[t]{1}
\centerline{\psfig{figure=fig1.eps,width=6cm,angle=0}}
%\includegraphics[width=0.5\linewidth,angle=0]{fig1.eps}
\caption{This figure illustrates an example of the decision-tree of $V$ for a fixed random bits $R$.
`Re' and `Ac' stand for 'Reject' and 'Accept' respectively.}
\label{fig1}
\end{psfrags}
\end{center}
\end{figure}
From $PCP$-Theorem,
we have a verifier $V$ which uses $O(\log n)$ random bits and query 3 bits from the oracle (or the proof $\pi$).
For a fixed random bits $R$, let $i_1$ be the index of the bit of $\pi$ where $V$ queries at the first time.
Depending on the value of $\pi_{i_1}$, $V$ may query the different index of $\pi$ at the second time; $i_2$ if $\pi_{i_1}=0$ and $i_3$ if $\pi_{i_1}=1$. Similarly, when $V$ query at the third time,
its query-index is one of $i_4,i_5,i_6$ and $i_7$. Now, there is no more query and it is decided whether
$V$ accepts or not based on these three queries.
If we consider each bit of the proof $\pi$ as a boolean variables $\pi_i$,
the decision of $V$ can be expressed as a 3SAT formula $\phi^R$.
For example, if $V$ rejects when $(\pi_{i_1},\pi_{i_2},\pi_{i_5})=(0,1,1)$,
$\pi_{i_1}\vee\bar{\pi}_{i_2}\vee\bar{\pi}_{i_5}$ should be one of clauses in $\phi^R$.
Figure \ref{fig1} illustrates this example. In this case,
$$\phi^R=(\pi_{i_1}\vee\pi_{i_2}\vee\pi_{i_4})\wedge
(\pi_{i_1}\vee\bar{\pi}_{i_2}\vee\bar{\pi}_{i_5})\wedge
(\bar{\pi}_{i_1}\vee\bar{\pi}_{i_3}\vee\pi_{i_7}).$$
Hence, $\phi^R$ consists of at most 8 clauses.
The reduction $f$ chooses $\phi=\wedge_R \phi^R$ and $t$ as the total number of clauses in $\phi$.
From the definition of $PCP$, if $x\in L$, then there exists a $\pi$ such that $V$ accepts.
In other words, if $x\in L$, $\phi$ is satisfiable.
On the other hand, if $x\notin L$, then $\forall \pi$, $V$ accepts $\pi$ with probability $\approx\frac12$.
Thus, if $x\notin L$, the number of unsatisfying $\phi^R$ is at least $\approx m/2$ for all $\pi$,
where $m$ is the total number of $R$.
Since $t\leq 8m$, the desired inequality follows: $OPT(\phi)\lesssim t-m/2\leq \frac{15}{16}t$.
\section{Dinur's Proof of $PCP$-Theorem}
Before stating the Dinur's main theorem, we first define the Generalized Graph $k$-coloring problem, say $GGC(k)$.
For a given graph $G=(V,E)$ and a function $\pi:E\times\{1,\dots,k\}\times\{1,\dots,k\}\rightarrow \{0,1\}$,
the Generalized Graph $k$-coloring problem is finding a coloring $\chi:V\rightarrow\{1,\dots,k\}$ such that
$\pi(e,\chi(u),\chi(v))=1$ for all $e=(u,v)\in E$.
Also, define
\begin{eqnarray*}
UNSAT(G,\chi)&=&\frac{\#~ \mbox{of edges $e=(u,v)$ s.t. }\pi(e,\chi(u),\chi(v))=0}{|E|},\\%~~\mbox{and}~~
UNSAT(G)&=&\min_{\chi}UNSAT(G,\chi).
\end{eqnarray*}
Now we state the Dinur's main theorem.
\begin{theorem}\label{thm:dinurmain}
For any $NP$-complete language $L$, there exist $k,\varepsilon>0$ and a poly-time reduction $f$ to the instance of $GGC(k)$ such that $f(x)=(G,\pi)$ and it satisfies the following:
\begin{itemize}
\item If $x\in L$, then $UNSAT(G)=0$.
\item If $x\in L$, then $UNSAT(G)\geq \varepsilon$.
\end{itemize}
\end{theorem}
It is not hard to see that Theorem \ref{thm:dinurmain} is equivalent to $PCP$-Theorem.
The key lemma behind Theorem \ref{thm:dinurmain} is following.
\begin{lemma}\label{lem:key}
$\exists k\footnote{In fact, Lemma \ref{lem:key} is true for all $k\geq 3$. However, to show Theorem \ref{thm:dinurmain}, it is enough to consider a specific $k$.},\varepsilon>0,f$ such that
% which maps $G,\pi$ to $\widehat{G},\widehat{\pi}$such that
\begin{itemize}
\item $f$ is a linear-time reduction with $GGC(k)\stackrel{f}{\longrightarrow} GGC(k)$ and $G\stackrel{f}{\longrightarrow} \widehat{G}$
\item $UNSAT(G)=0 ~\Rightarrow~ UNSAT(\widehat{G})=0$
\item $UNSAT(\widehat{G})\geq \min\{\varepsilon,2\cdot UNSAT(G)\}$.
\end{itemize}
\end{lemma}
We call Lemma \ref{lem:key} as {\em Amplifying Lemma} since the reduction $f$ amplifies $UNSAT$ while
preserving the order of the graph i.e. $|\widehat{G}|=O(|G|)$. Initially, $G$ may have $UNSAT(G)\in\left\{0,\frac1{|E|}\right\}$ in the worst case. Apply $f$ to $G$ to get a new graph $G\leftarrow \widehat{G}$
such that $UNSAT(G)\in\left\{0,\frac2{|E|}\right\}$. Similarly, we iteratively apply $f$ to $G$
until we obtain $UNSAT(G)\in\{0\}\cup [\varepsilon,1]$.
This procedure needs at most $O(\log |E|\varepsilon)=O(\log |G|\varepsilon)$ iterations. Since the size of $G$ blows up by a constant factor
at each iteration, the size of $G$ which we finally obtained is $O(1)^{O(\log |G|\varepsilon)}=\poly(|G|)$.
Therefore, using the fact that $GGC(k)$ is $NP$-complete,
we can completes the proof of Theorem \ref{thm:dinurmain}.
Now we sketch the proof of Lemma \ref{lem:key}. Its proof needs the following two lemmas.
\begin{lemma}\label{lem:one}
$\forall k, C$ $\exists K,\varepsilon_0>0,f$ such that
\begin{itemize}
\item $f$ is a linear-time reduction with $GGC(k)\stackrel{f}{\longrightarrow} GGC(K)$ and $G\stackrel{f}{\longrightarrow} \widehat{G}$
\item $UNSAT(G)=0 ~\Rightarrow~ UNSAT(\widehat{G})=0$
\item $UNSAT(\widehat{G})\geq \min\{\varepsilon_0,C\cdot UNSAT(G)\}$.
\end{itemize}
\end{lemma}
\begin{lemma}\label{lem:two}
$\exists k, \delta>0$ $\forall K$ $\exists f$ such that
\begin{itemize}
\item $f$ is a linear-time reduction with $GGC(K)\stackrel{f}{\longrightarrow} GGC(k)$ and $G\stackrel{f}{\longrightarrow} \widehat{G}$
\item $UNSAT(G)=0 ~\Rightarrow~ UNSAT(\widehat{G})=0$
\item $UNSAT(\widehat{G})\geq \delta \cdot UNSAT(G)$.
\end{itemize}
\end{lemma}
Choose $k,\delta$ from Lemma \ref{lem:two} and then
let $C=2/\delta$ for Lemma \ref{lem:one}.
Hence, naturally we choose the reduction $f$ in Lemma \ref{lem:key} as $f=f_2 \circ f_1$ where
$f_1$ and $f_2$ are linear reductions in Lemma \ref{lem:one} and Lemma \ref{lem:two} respectively.
If $G\stackrel{f_1}{\longrightarrow}\widehat{G}\stackrel{f_2}{\longrightarrow}\widetilde{G}$,
\begin{eqnarray*}
UNSAT(G)=0 &\Rightarrow& UNSAT(\widehat{G})=0~~\Rightarrow~~ UNSAT(\widetilde{G})=0,\\
UNSAT(\widetilde{G})&\geq& \delta \cdot UNSAT(\widehat{G})\\
&\geq&\delta\cdot \min\{\varepsilon_0,\frac2{\delta} \cdot UNSAT(G)\}\\
&\geq&\min\{\varepsilon_0\delta,2 \cdot UNSAT(G)\}.
\end{eqnarray*}
Hence, we can choose $\varepsilon=\varepsilon_0\delta$ for Lemma \ref{lem:key}.
In the next lecture, we will study the proof of Lemma \ref{lem:two}.
\end{document}