\documentclass{article}
\usepackage{amssymb}

\begin{document}
\input{preamble.tex}
\lecture{19}{April 13, 2005}{Madhu Sudan}{Kevin Matulef}

\section{Today}

\begin{itemize}
\item We finish the proof that NP $\subseteq$ PCP[$\poly\log n, \poly\log n$].
\item We give another PCP construction, showing NP $\subseteq$ PCP[$\poly(n),O(1)$].
\end{itemize}

\section{Review: Graph Coloring PCP}

Last time we began a PCP construction for graph $3$-colorabilty.  Recall that 
\begin{itemize}
\item The vertices were labeled by elements of some sufficiently large field $\F$.  
\item The edges were given by a function $E: \F \times \F \rightarrow \F$.  
\end{itemize}

The prover writes down  

\begin{itemize}
\item A coloring given by a polynomial $\chi : \F \rightarrow \F $ where degree $\chi \le n$
\item A polynomial  $A : \F \rightarrow \F $ defined by  $ A(x) = \chi(x)(\chi(x)-1)(\chi(x)-2)$ so that $A|_V = 0$.  
\item A polynomial $B : \F \times \F \rightarrow \F$ defined by $B(x,y) = E(x,y) \prod_{j \in \{-2,-1,1,2\}}(\chi(x)-\chi(y)-j)$ so that $B|_{V\times V} = 0$

\end{itemize}

Last time we discussed how a verifier can check this proof.  All we have left to show is how the verifier can check that the function tables for $\chi,A,B$, etc. indeed represent low-degree polynomials.

\section{Low Degree Test}

Our task is thus: given an oracle $f: \F^n \rightarrow \F$, and an integer $d$, we want
to sample $f$ on only $q$ locations, and then 
\begin{itemize}
\item If $\F$ is an $m$-variate degree $d$ polynomial $\Rightarrow$ accept wp 1.
\item If $\F$ is $\delta$-far from every such polynomial $\Rightarrow$ reject wp $\ge \epsilon$.
  
\end{itemize}

Here, by $\delta$-far, we mean $\Pr_{x \in \F^m}[f(x) \neq g(x)] \ge \delta$ 

The number of queries, $q$, will depend on $m,d,|\F|,\delta$,and
$\epsilon$.  In the univariate case,
when $m=1$, it is easy to see that the test must make more than $d$
queries.  If it makes fewer that that, then there is always a degree
$d$ polynomial consistent with the values it has seen.  Thus, it will
not have enough information to reject, even if the rest of the table
is inconsistent with such a polynomial.  

We will give a test that, for constant $\epsilon, \delta$ (say both
equal to $0.1$), makes a number of queries $q$ that depends polynomially on $d$.  There is
also a small dependence on $m$, but not enough to matter for our purposes,
so we omit it.

It is easy to come up with such a test for
univariate polynomials.  We simply make $d+1$ queries, interpolate to
get a polynomial, then test to see if that polynomial is consistent
with the rest of the table by querying another point.  More formally, here is our test for $m=1$.

\begin{itemize}

\item Pick distinct $\alpha_1, \alpha_2, ... , \alpha_{d+1} \in \F$.
\item Query $f(\alpha_1), f(\alpha_2), ... , f(\alpha_{d+1})$.  
\item Let $p(x)$ be a degree $d$ polynomial st $p(\alpha_i) = f(\alpha_i)$ for all $i$.   
\item Pick $\alpha_{d+2} \in \F$ randomly.  
\item Query $f(\alpha_{d+2})$.  
\item Check if $p(\alpha_{d+2}) = f(\alpha_{d+2})$. If so, \emph{accept}.  Otherwise, \emph{reject}.  

\end{itemize}

To generalize this to $m$-variate polynomials, we can pick a random line, and then test that the points on this line are consistent with a univariate degree $d$ polynomial.  More formally, here is the test for arbitrary $m$:

\begin{itemize}
\item Pick $\beta,\gamma \in \F^m$.  
\item Let $\ell_{\beta,\gamma} : \F \rightarrow \F^m$ be defined by $\ell_{\beta,\gamma}(t) = \beta t + \gamma$. 
\item Let $f|_{\ell_{\beta,\gamma}} : \F \rightarrow \F $ be defined by $f|_{\ell_{\beta,\gamma}}(t) = f(\ell_{\beta,\gamma}(t))$.  

\item Verify that $f|_{\ell_{\beta,\gamma}}$ is a univariate polynomial of degree $d$ using the univariate test given earlier.  

\end{itemize}

Intuitively, this is a very natural extension of the univariate test.
However, proving that it succeeds with sufficiently high probability
is not easy, because it is hard to characterize those functions
which are far from multivariate polynomials.  Nonetheless, it can be
shown that the test works.  While we will not prove it here, we
state the following (the full proof can be found in a paper by Arora, Lund, Motwani, Sudan, and Szegedy):

\begin{lemma}
If $\Pr[\textrm{test rejects } f] \le \epsilon$ (for $\epsilon \approx 0.1$, and $|\F| \ge \poly(\frac{d}{\epsilon \delta m})$), then $f$ is $2\epsilon$-close to some polynomial $p$.  
\end{lemma}

\section{Reducing the Number of Queries}

Now we have shown how to test that polynomials have degree $d$, by
making $\poly(d)$ queries.  However, in the PCP construction that we
have given so far, we need to test that some polynomials have degree
$n$.  This requires making $\poly(n)$ queries into the proof.  But
this is silly, since $3$-colorability has proofs of size $O(n)$.  With $\poly(n)$ queries, we could just look at the whole proof.  To fix this, we
change the way the proof is encoded.  Instead of encoding the vertices
as elements of a field $\F$, we let $\F$ be a smaller field, and encode vertices as vectors in $\F^m$.  Specifically:

\begin{itemize}

\item Let $|\F| \approx \log^3n$.
\item Let $H \subseteq \F$, $|H| = \log n$.
\item Let $V \approx H^m$, so $m = \frac{\log |V|}{\log |H|} = \frac{\log n}{\log \log n}$.
\item Now $E: H^m \times H^m \rightarrow \{0,1\}$, and we extend to get $\hat{E} : \F^m \times \F^m \rightarrow \F$.

\end{itemize}

Accordingly, the prover changes the domain of the functions written down.  So the prover writes:

\begin{itemize}

\item $\chi : \F^m \rightarrow \F $ 
\item $A : \F^m  \rightarrow \F $.
\item $B : \F^m \times \F^m \rightarrow \F$
 
\end{itemize}

Note that $|\F^m| = ((\log n)^3)^\frac{2\log n}{\log \log n} = n^6$, so the size of the proof is still polynomial.  Now the verifier's task is to:

\begin{itemize} 

\item verify the degrees of $\chi, A, B,$ etc.  But notice now that the degree of each of these polynomials is $O(\poly\log n)$ instead of $n$.  Since the polynomials are $m$-variate instead of univariate, they needn't be of high degree to have the correct values on $n$ or $n^2$ points.

\item verify that $\chi$ is consistent with $A$, and that $\chi$ and $E$ are consistent with $B$.  

\item verify that $A|_{H^m} = 0$ and $B|_{H^m \times H^m} = 0$.  This can be done using the method outlined in the last lecture.   Notice that $A(\overline{\alpha}) = 0$ for all $\overline{\alpha} \in H^m$, if and only if $A$ can be written as $A(x) = \sum_{i=1}^{m}A_i(x)g(x)$ where $g(x) = \prod_{\beta \in H}(x-\beta)$ and $A_1,...,A_m$ are polynomials.  

Thus, we modify the protocol so that the prover sends the additional polynomials $A_1,...,A_m : \F^m \rightarrow \F$ and  $B_1,...,B_{2m} : \F^{2m} \rightarrow \F$.  The verifier then tests the degrees of  $A_1,...,A_m$ and $B_1,...,B_{2m}$.  The verifier also tests that $A$ is of the correct form by checking $A(\gamma) = \sum_{i=1}^m A_i(\gamma)g(\gamma)$ for some random $\gamma$.  A similar test is done for $B$.

\end{itemize}

This completes the description of the PCP construction, showing that NP $\subseteq$ PCP[$\poly\log n, \poly\log n$].

\section{A Different PCP}

Now we outline a different PCP construction where the verifier uses a
polynomial amount of randomness but only makes a constant number of
queries into the proof.  To start, consider the following problem (it is an exercise
to show that this is NP-hard).  Given $m$ degree-$2$ polynomials $P_1,...P_m$ on $n$ variables over
$GF(2)$, find an assignment to $x_1,...x_n \in GF(2)$ that makes all the polynomials simultaneously evaluate to zero.   

Suppose $a_1,...a_m$ is such an assignment.  To convince the verifier of this, the prover writes down

\begin{itemize}
\item for every linear function $\ell: \F_n^n \rightarrow \F_2$, the value $\ell(\overline{a})$.  Store all these values in a table $T_1$. There are $2^n$ linear functions (parity functions) so the table has length $2^n$.  

 
\item for every quadratic function $q : \F_2^n \rightarrow \F_2$, the value $q(\overline{a})$.  Store all these values in a table $T_2$.  There are $2^{n^2}$ quadratic functions so the table has length $2^{n^2}$. 
\end{itemize}
 
The verifier then

\begin{enumerate}

\item verifies $\exists a$ st $T_1[\ell] = \ell(a)$ for most $\ell$

\item verifies $\exists a$ st $T_2[q] = q(a)$ for most $q$.  

\item Picks $r_1,...r_m \in \{0,1\}$ at random, then verifies that the polynomial $q(a) \triangleq \sum r_i P_i(a)$ is zero.  

\end{enumerate}

Step 1 is accomplished by choosing $\ell_1$ and $\ell_2$ at random,
and checking that $T_1[\ell_1] + T_1[\ell_2] = T_1[\ell_1 + \ell_2]$.
This is an application of the well-known linearity test by Blum, Luby, and Rubinfeld.
We will not analyze it here.

Step 2 is accomplished with two separate checks.  The verifier first
chooses $q_1$ and $q_2$ randomly, then checks that $T_2[q_1] +
T_2[q_2] = T_2[q_1+q_2]$.  Next the verifier checks that $T_1[\ell_1]
\cdot T_1[\ell_2] = T_2[q_2 + \ell_1\cdot\ell] - T_2[q_2]$.

Step 3 is accomplished as follows: the verifier picks a random quadratic function $q_2$ on $n$ variables, and checks that $T_2[q_2+ q] = T_2[q_2]$.  As long as $T_2$ is only corrupted a small amount, this test is likely to pass when $a$ makes all the $P_i$'s (and hence $q$) zero.

The total number of queries performed in all three steps is just 12,
which is constant.  Notice however that each query requires producing $O(n)$ or $O(n^2)$ bits simply to index into the tables $T_1$ or $T_2$.  This shows that NP $\subseteq$ PCP[$\poly(n),O(1)$].  

\section{Further Reducing the Number of Queries}

One way to reduce the number of queries further is to perform just one of
the checks at random from the checks above.  This reduces the number
of queries to $4$, at the cost of a higher error rate. 

Hastad has given a PCP construction that goes even further and reduces
the number of queries to a mere 3.  We will attempt to give a sketch of
his approach here (DISCLAIMER:  I do not understand what follows. After this point I am mindlessly transcribing 
from my notes).


Conisder the following formulation of satisfiability.  Given a function $f$ on $n$ variables over GF(2), find $a$ such that $f(a) = 1$.   

Now suppose $a_1,...,a_n$ is a satisfying assignment.  Let $T$ be a table which holds the value $g(a)$ for every possible function $g$.  Hastad performs a test that looks something like checking $T[g_1] + T_[g_2] = T[g_1 + g_2 + \eta]$ where $\eta$ is chosen randomly.  Actually, this is insufficient and the test is more like $T[g_1\wedge f] + T_[g_2\wedge f] = T[(g_1 + g_2 + \eta)\wedge f]$.  To disallow a table of all zeros from passing the test, the prover is asked to only write down half of the functions $g$.  The other half is implicity specified as the complement of the functions written down.  Thus if the prover writes down zeros, the implicit complement functions will yield ones.  


\end{document}