\documentclass[11pt]{article}
\usepackage{amsmath}
%\usepackage{amsthm}
\usepackage{amssymb}
\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in
\begin{document}
\input{preamble.tex}
\newcommand{\PCP}[1]{\ensuremath{\mathrm{PCP}[#1]}}
\lecture{18}{April 11, 2005}{Madhu Sudan}{Jonathan Kelner}
\section{Introduction}
In the last lecture, we defined probabilistically checkable proofs (PCPs) and
started to discuss how varying the amount of randomness and the number of
queries available to the verifier affects the class of languages that a PCP can
be constructed to accept. For completeness, we recall the definition of a PCP:
\begin{definition}
A language $L$ is in the class $\PCP{r(n),q(n)}$ if there exists a probabilistic
polynomial time oracle machine $V$ (called the \emph{verifier}) with access to
an input string $x$ and with oracle access to a \emph{proof} $\pi$ such that:
\begin{itemize}
\item $V$ tosses $r(|x|)$ coins, obtaining the random string $R$.
\item $V$ makes at most $q(|x|)$ oracle queries.
\item $V$ outputs an accept/reject verdict $V^{\pi}(x,R)$ such that
\begin{itemize}
\item If $x\in L$ then $V^{\pi}(x,R)$ accepts for all $R$.
\item If $x\not\in L$ then for all $\pi$,
$\mathrm{Pr}_R [V^{\pi}(x,R) \text{ accepts}] \le 1/2$.
\end{itemize}
\end{itemize}
\end{definition}
Today we shall begin the proof that $\mathrm{NP}\subseteq
\PCP{\mathrm{polylog}(n), \mathrm{polylog}(n)}$. Before we can do that, we
shall need some mathematical preliminaries.
\section{Algebraic Background}
In this and all subsequent sections, let $\F$ be a finite field, and let
$H=\{\alpha_1,\dots,\alpha_n\}\subseteq \F$ be a collection of distinct field
elements.
We shall rely heavily on the ability to perform interpolation with low degree
polynomials. The univariate form of this is quite well-known:
\begin{theorem}[Univariate Interpolation]
\label{univariate interpolation}
Let $\F$ and $H$ be as above, and let $f:H\rightarrow \F$ be arbitrary. Then
there exists a polynomial $\widehat{f}:\F\rightarrow \F$ of degree at most $n$
such that $\widehat{f}(\alpha)=f(\alpha)$ for all $\alpha\in H$.
\end{theorem}
\noindent A slightly less well-known version of this holds for multivariate
polynomials as well:
\begin{theorem}[Multivariate Interpolation]
\label{multivariate interpolation}
Let $f:H^m \rightarrow \F$. There exists a multivariate polynomial
$\widehat{f}:H^m\rightarrow \F$ such that $\widehat{f}(\alpha)=f(\alpha)$ for
all $\alpha\in H^m$. Furthermore, $\widehat{f}$ has degree at most $n=|H|$ in
each variable, so it has total degree at most $mn=m|H|$.
\end{theorem}
\noindent We shall also make use of the following algebraic fact, which follows
easily from the division algorithm:
\begin{theorem}
\label{univariate divisibility}
Let $g(x)=\prod_{\alpha\in H}(x-\alpha)$. $A$ is a polynomial with
$A(\alpha)=0$ for all $\alpha\in H$ if and only if $g(x)|A(x)$.
\end{theorem}
Theorem~\ref{univariate divisibility} doesn't hold for multivariate
polynomials, but there is a slight variant of it that remains true:
\begin{theorem}
\label{multivariate divisibility}
Let $g(x)=\prod_{\alpha\in H}(x-\alpha)$, and suppose that $B:\F^m\rightarrow
\F$ has $B(\gamma)=0$ for all $\gamma\in H^m$. Then $B$ can be written as a sum
$$B(x_1,\dots,x_m)=\sum_{i=1}^m Q_i(x_1,\dots,x_m)\cdot g(x_i),$$
i.e., $B$ can be written as a sum of a collection of terms, each of which is
divisible by $g(x_i)$ for some $i$.
\end{theorem}
\section{Graph 3-Coloring}
We now return to PCPs by describing a PCP for graph 3-coloring. Let $G=(V,E)$ be
a graph. A 3-coloring is a map $\chi:V\rightarrow \{0,1,2\}$ such that for all
$(x,y)\in E$, $\chi(x)\ne \chi(y)$.
We can write this in a more functional form. Treat the edge set as a map
$E:V\times V\rightarrow \{0,1\}$. A graph has a 3-coloring if and only if there
exists some map $\chi:V\rightarrow \{0,1,2\}$ such that for all $(x,y)\in V\times
V$, either $E(x,y)=0$ or $\chi(x)\ne \chi(y)$.
In order to make a PCP for this, we must first rephrase it in a more algebraic
way. To do this, we assume that $\F$ is ``large enough,'' say $|\F|>10 |V|$,
and that it does not have characteristic 2, so that 0, 1, and 2 are distinct
elements. We then treat $V$ as a subset of $\F$, say by assigning the
$i^\text{th}$ element of $\F$ to the $i^\text{th}$ vertex.
Now, by multivariate interpolation, we
can extend $E$ to a map $\widehat{E}: \F\times\F \rightarrow \F$ so that
$\widehat{E}$ equals $E$ when restricted to $V\subseteq \F$. Furthermore, we
can take $\widehat{E}$ to have degree at most $2n$ (where $n=|V|$). Now, a
3-coloring exists if and only if there exists a map $\chi:\F\rightarrow \F$ of
degree $n$ such that:
\begin{enumerate}
\item $B(x,y):=\widehat{E}(x,y)\cdot
\prod_{j\in\{-2,-1,1,2\}}(\chi(x)-\chi(y)-j)=0$ for all $x,y\in V$.
\item $A(x):=\chi(x)(\chi(x)-1)(\chi(x)-2)=0$ for all $x\in V$.
\item $\deg(A(x))\le 3n$.
\item $\deg(B(x))\le 6n$.
\end{enumerate}
We shall now discuss how to construct a PCP for these four properties.
\section{Proving 3-Colorability}
In our first cut at a PCP, the prover will write down truth tables for $\chi$,
$A$, and $B$. The verifier will then verify:
\begin{enumerate}
\item The degrees of $\chi$, $A$, and $B$ are small.
\item The values given for $A$ and $B$ are consistent with those given for
$\chi$.
\item $A$ is zero on $V\subseteq \F$, and $B$ is zero on $V\times V \subseteq
\F \times \F$.
\end{enumerate}
We address these three properties in turn.
\subsection{Low Degree Testing}
All of the tests for property 1.\ are instances of \emph{low degree
testing}. We are given oracle access to a function $f:\F^m\rightarrow \F$, and
we are charged with determining if $f$ is of some degree $d$. We do this by
making some small number of (possibly random) queries to the oracle, and we are
required to succeed with some good probability.
Unfortunately, this is impossible. Suppose we started with some function $f$
that was of degree $d$ and modified its value at one point so that it became of
much larger degree. (For example, the zero function is of degree zero, but a
function that is nonzero at exactly one point is of degree $|\F|-1$.) There is no
way that we could distinguish the original function from the modified one
without making a number of queries that is linear in the field size. As such,
we shall content ourselves with a weaker notion: we shall test if a function is
``close'' to a low degree polynomial.
\begin{definition}
Two polynomials $f,g:\F\rightarrow \F$ are \emph{$\delta$-close} if
$\mathrm{Pr}_x[f(x)\ne g(x)]\le \delta$.
\end{definition}
\begin{definition}
A \emph{$(d,k,\epsilon,\delta)$ low degree tester} is a probabilistic algorithm
with oracle access to a function $f$ that:
\begin{itemize}
\item makes at most $k$ oracle queries,
\item always accepts if a polynomial $f$ is of degree at most $d$, and
\item rejects with probability at least $1-\epsilon$ if there is no degree $d$
polynomial $\widehat{f} $that is $\delta$-close to $f$.
\end{itemize}
\end{definition}
In the next lecture, we'll talk about how to construct low degree testers and
for what parameter ranges they exist. For the remainder of this lecture, we'll
just assume that we have one that does what we need it to do.
\subsection{Consistency Testing}
Testing consistency in property 2.\ turns out to be quite easy, assuming that we
have already tested that the polynomials in question have low degree. Testing
whether $A$ and $\chi$ are consistent amounts to testing whether
$$A(x)=\chi(x)(\chi(x)-1)(\chi(x)-2).$$
We do this by randomly choosing a value of $x$ and verifying that equality
holds. This test never falsely rejects. Furthermore, if $A$ and $\chi$ are
polynomials of respective degrees $3n$ and $n$ and they are inconsistent, this
test will reject with probability at least $1-3n/|\F|$.
Our low degree testing can't tell us that $A$ and $\chi$ are of the appropriate
degrees; it can only tell us that they are $\delta$ close to polynomials of the
appropriate degree. This doesn't cause any real problems though---our test will
now find errors with probability at least $1-3n/|\F|-2\delta$. (We pick an $x$
where either $A$ or $\chi$ differs from its nearby low degree polynomial with
probability at most $2\delta$.)
We can thus verify that $A$ and $\chi$ are consistent with only two queries. A
similar argument allows us to test that $B$ and $\chi$ are consistent with three
queries: we randomly pick $x$ and $y$ and verify that
$$ B(x,y)=\widehat{E}(x,y)\cdot
\prod_{j\in\{-2,-1,1,2\}}(\chi(x)-\chi(y)-j).$$
\subsection{Testing Whether A,B=0 When They Should Be}
To test property 3., the na\"ive approach would be to just randomly pick values
where $A$ and $B$ should be zero, evaluate them, and verify that they vanish.
Unfortunately, this doesn't work, since we need to verify that $A$ and $B$
vanish at all values in $V$ and $V\times V$, respectively, not just at most such
values, and we'd have to make way too many queries to verify this fact with
reasonable probability.
Instead, we use Theorems~\ref{univariate divisibility} and~\ref{multivariate
divisibility}. To test whether $A$ is zero at the appropriate locations, let
$g(x)=\prod_{\alpha\in H}(x-\alpha)$. By Theorem~\ref{univariate divisibility},
it suffices to check whether $g(x)$ divides $A(x)$, i.e., whether there exists
some $R_A(x)$ such that $A(x)=R_A(x)g(x)$. To do this, we slightly modify the
protocol by having the prover send a table for $R_A(x)$ as well. We are now
back to cases we have already analyzed: we verify that $R_A(x)$ is of low degree
and that $A$, $R_A$, and $g$ are consistent. (As before, it suffices to check
whether $R_A$ is close to a low degree polynomial.)
To verify that $B$ is zero, we use Theorem~\ref{multivariate divisibility}. If
$B$ is zero on $V\times V$, there are some polynomials $Q_B$ and $R_B$ such that
$B(x,y)=Q_B(x,y)g(x)+R_B(x,y)g(y)$. The prover will send $Q_B$ and $R_B$, and, as
above, we can check the degrees and consistency.
We would therefore be done if we could actually perform the asserted low degree
testing. This will be discussed in the next lecture.
\end{document}