\documentstyle[epsfig]{article}

\textwidth=6in
\oddsidemargin=0.25in
\evensidemargin=0.25in
\topmargin=-0.1in
\footskip=0.8in
\parindent=0.0cm
\parskip=0.3cm
\textheight=8.00in
\setcounter{tocdepth} {3}
\setcounter{secnumdepth} {2}
\sloppy 

\def\F{\mbox{$\cal F$}} 
\def\X{\mbox{$\cal X$}} 
\def\S{\mbox{$\cal S$}} 

\begin{document}
\input{preamble.tex}
\lecture{21}{May 21, 1999}{Daniel A. Spielman}{Louay Bazzi}

\section{From Last Lecture}

We recall from the last lecture that  a language $L$ is 
PCP$(r(n),q(n))$ if $\exists$ a polynomial time 
verifier $V$ with access to $O(r(n))$ random bits and 
random access to a proof $\Pi$, of which it can read $O(q(n))$ 
random bits such that : 
\begin{itemize} 
\item[] $w\in L  \Rightarrow \exists\mbox{ } \Pi $ s.t. Pr$[V(w,\Pi)$ accepts 
$]$ = 1
\item[]  $w\not\in L  \Rightarrow \forall\mbox{ } \Pi $, Pr$[V(w,\Pi)$ accepts 
$] < 1/2$.
\end{itemize}  

Our objective was to prove 
\begin{theorem}
3SAT $\in $ PCP$(\log^{O(1)}{n},\log^{O(1)}{n})$. 
\end{theorem}

Say that $\phi$ is a 3CNF over $n$ variables.  We argued that 
we  will encode an assignment $a$ of $\phi$ using 
an error correction code as follows. 
Think of $a$ as function 
from $\{0,1\}^m$ to $\{0,1\}$ ($m=\log{n}$), 
take the (unique) multi-linear extension $A$ of this 
function over a field 
$\F$  whose size is $\Theta(m^2)$, and  
represent $A$ as a table  
$T:\F^m\rightarrow \F$  whose size is $O(2^{O(\log^{O(1)}{n})})$. 


Then we proposed a test that given any table $T$ can efficiently 
check if it is a multi-linear extension in the sense that: 
1) If $T$ is multi-linear then always accept
2) If probability of acceptance is $>1/100$ then $\exists$ 
a multi-linear $A$ s.t.
\[
\mbox{Pr}_{V_1,\ldots,V_n\in \F}[A(V_1,\ldots,V_n) = T(V_1,\ldots,V_n) ] > 
99/100
\]
3) the test uses  ${O(\log^{O(1)}{n})}$   random bits and 
reads only  $O(\log^{O(1)}{n})$  bits  from the table. 

At the end of last class we began to arithmetize $\phi(x_1,\ldots,x_n)$. 
We were looking for an arithmetization that enables the verifier to 
check through an IP protocol 
if the assignment given by the table is a satisfying assignment. The 
big picture is that the verifier will use a number of random
bits polynomial in $m$ and hence poly-logarithmic in $n$. The number of bits 
that the prover sends to the verifier is also poly-logarithmic in $n$.
To turn this into a PCP, will store in the probabilistically 
checkable proof,  in addition to the 
table $T$, all the responses of the prover indexed by the IP 
verifier random bits. So, the PCP 
verifier will first perform the multi-linearity test on the table, 
and then will engage in an  IP protocol with the proof. 

To arithmetize $\phi$, we started by arithmetizing each of its  clauses.
For any  clause $c$ of $\phi$, we constructed a formula CC$(A,c)$ that 
is $0$ iff $A$ satisfies $c$. The Clause Check is given by 
\[
CC(A,c) = 
\sum_{
\begin{array}{l}
V_1^{(1)},\ldots,V_m^{(1)}\in \{0,1\} \\
V_1^{(2)},\ldots,V_m^{(2)}\in \{0,1\} \\
V_1^{(3)},\ldots,V_m^{(3)}\in \{0,1\} 
\end{array}
}
\Pi_{j=1}^3 \X_{j,c}(V_1^{(j)},\ldots,V_m^{(j)})
\left( \S_{j,c} - A(V_1^{(j)},\ldots,V_m^{(j)}) \right),  
\] 
where $\X_{j,c}$  is the  multi-linear extension 
of the boolean function  $X_{j,c}:\{0,1\}^m\rightarrow \{0,1\}$
given by 
\[
X_{j,c}(V_1,\ldots,V_m) = 
%\mbox{ 
\left\{
\begin{array}{ll}
1 &  \mbox{if the index of $j$th variable of clause $c$ is $V_1,\ldots,V_m$ in 
binary }\\
0 &  \mbox{otherwise} , 
\end{array} 
\right\}
\]
and 

\[
S_{j,c}=  \left\{ 
%\mbox{
\begin{array}{ll} 
1 & \mbox{ if the $j$th variable of clause $c$ is not negated } \\
0 & \mbox{ otherwise }.
\end{array}  
%} 
\right.
\]

\section{Completing the Arithmetization}
   We have a clause check $CC(A,c)$ that is zero iff $A$ satisfies 
$c$. We want something like $CC$, but equal to zero iff all the 
clauses of $\phi$ are satisfied. 
There are many ways to do this, but the following will  prove 
helpful later in the proof. The idea is use some randomness.
To get started, consider 
$
\sum_{c} r_c CC(A,c), 
$
where the sum is over the clauses of $\phi$, and the 
$r_c$'s  are chosen at random from $\F$.
Since $\F$ is large enough, with a high probability   this sum 
is zero  iff $A$ satisfies  
all the clauses. But there is a problem  with this approach, 
it requires too many random bits. To fix the problem we use 
pseudo randomness. Say that $\phi$ has $t$ clauses 
$c_1,\ldots, c_t$ , and  assume that $t$ is a power of $2$,
say $2^s$
(if this not the case we can always duplicate some clauses).
Also if $a\in \{0,1\}^{s}$, let $c_a$  mean $c_k$, where 
$a$ is the binary representation of $k$. 
Now, consider the Formula Check 
\[
FC(\phi,A) = 
\sum_{a\in \{0,1\}^s} r_1^{a_1}\ldots r_s^{a_s} CC(A,c_a),
\]
where $r_1,\ldots,r_s$ are chosen at random $\F$.
This requires only $O(s\log{|\F|}) = O(m\log{m})$ random bits only (
recall that $|\F| = \Theta(m^2)$). 
On the other hand, if we look at $FC(\phi,A)$ as a multi-linear polynomial in 
$r_1,\ldots,r_s$, it follows immediately from 
Shwarz Lemma that 
\begin{eqnarray*}
&& \mbox{Pr}_{r_1,\ldots,r_s\in \F}\left[FC(\phi,A) = 0 
\mbox{ iff $A$ satisfies all the clauses of $\phi$} \right]   
\\&& \mbox{ } \mbox{ } \mbox{ } \mbox{ } 
\geq  1 - \mbox{Pr}_{r_1,\ldots,r_s\in \F}\left[ (r_1,\ldots,r_n) \mbox{ is a 
zero of } FC(\phi,A)\right]
\\&& \mbox{ } \mbox{ } \mbox{ } \mbox{ } 
\geq   1 - {s\over{|F|}} = 1 - O\left({1\over{m}}\right).
\end{eqnarray*} 

The verifier needs to be convinced that $FC(\phi,A) = 0$. 
To make this suitable for the IP machinery, we  use 
the definition of $CC(A,c_a)$, to  
express $FC(\phi,A)$ as
\[
FC(\phi,A) = 
\sum_{
\begin{array}{l}
V_1^{(1)},\ldots,V_m^{(1)}\in \{0,1\} \\
V_1^{(2)},\ldots,V_m^{(2)}\in \{0,1\} \\
V_1^{(3)},\ldots,V_m^{(3)}\in \{0,1\} 
\end{array}
}
Q(V_1^{(1)},\dots,V_m^{(3)}), 
\]
where 
\[
Q(V_1^{(1)},\dots,V_m^{(3)}) = \sum_{a\in \{0,1\}^s} r_1^{a_1}\ldots r_s^{a_s} 
\Pi_{j=1}^3 \X_{j,c}(V_1^{(j)},\ldots,V_m^{(j)})
\left( \S_{j,c} - A(V_1^{(j)},\ldots,V_m^{(j)}) \right).
\] 

Observe that $Q$ is of degree at most $6$  in each $V_i^{(j)}$
and of degree at most $6m$ in all the $V_i^{(j)}$'s. 
This is because $\X_{i,c}(V_1^{(j)},\ldots,V_m^{(j)})$ 
and $\S_{j,c} - A(V_1^{(j)},\ldots,V_m^{(j)})$ are 
both multi-linear.




\section{ The IP protocol } 

The interactive proof of $FC(\phi,A) = 0$ is very similar to
the one we used for $\#$SAT. 

\begin{enumerate}
 
\item   
$P$ sends to $V$ the coefficients of $\hat{Q}_1(z)$, a polynomial 
claimed to be equal to  
\[
Q_1(z) = \sum_{V_2^{(1)},\ldots, V_m^{(3)}\in \F}Q(z,V_2^{(1)},\dots,V_m^{(3)})
.
\]
$V$ checks if $\hat{Q}_1(0) + \hat{Q}_1(1) = 0$. If this is not true then  
$V$ rejects, else $V$
selects $a_1$ randomly from $\F$, and send it to $P$.   \\
($P$ convinces $V$ that $FC(\phi,A)=0$ with a high 
probability if $\hat{Q}_1(a_1)=Q_1(a_1)$) 


\item[.\mbox{ }]
\item[.\mbox{ }]
\item[.\mbox{ }]

\item[i.] 
$P$ sends to $V$ the coefficients of $\hat{Q}_i(z)$, a polynomial 
claimed to be equal to  
\[
Q_i(z) = \sum_{V_{?}^{(?)},\ldots, V_m^{(3)}\in \F}Q(a_1,\ldots,a_{i-1},z,V_{?}
^{(?)},\dots,V_m^{(3)}).
\]
$V$ check if $\hat{Q}_i(0) + \hat{Q}_i(1) = \hat{Q}_{i-1}(a_{i-1})$. If this 
is not true then
$V$ rejects, else $V$
selects $a_{i}$ randomly from $\F$, and send it to $P$.   \\
($P$ convinces $V$ that $\hat{Q}_{i-1}(a_{i-1})=Q_{i-1}(a_{i-1})$
with a high probability if $\hat{Q}_{i}(a_{i})=Q_i(a_i)$ ) 


\item[.\mbox{ }]
\item[.\mbox{ }]
\item[.\mbox{ }]

\item[3m.] 
$P$ sends to $V$ the coefficients of $\hat{Q}_{3m}(z)$, a polynomial 
claimed to be equal to 
\[
Q_{3m}(z) = Q(a_1,\ldots,a_{3m-1},z).
\] 
$V$ checks if $\hat{Q}_{3m}(0) + \hat{Q}_{3m}(1) = \hat{Q}_{3m-1}(a_{3m-1})$ 
If this is not true then  $V$ rejects, else $V$
selects $a_{3m}$ randomly from $\F$, and checks     
if $\hat{Q}_{3m}(a_{3m}) = Q(a_1,\ldots,a_{3m})$, by 
computing the later from the table. 
If this is not true then  $V$ rejects. \\
($V$ checks if the value of $\hat{Q}_{3m}(a_{3m})$ is correct 
according to  the table) 
\end{enumerate}

If $FC(\phi,A) = 0$ then, there exists an 
``honest'' prover and ``perfect'' table  such that 
the verifier accepts with a probability 1. Here 
by a ``perfect'' table, we mean a one that contains 
the correct values of $A$ in all its entries. 


If on the other-hand $FC(\phi,A) \neq 0$, then , for any 
prover $P$,  $V$ may accepts due two possible reasons:
\begin{itemize}       
\item  Either  $P$ 
remained  consistent by keeping on sending 
polynomials $\hat{Q}_i(z)\neq Q_i(z)$ 
but satisfying $\hat{Q}_1(0)+\hat{Q}_ 1(1)=0$ and  
$\hat{Q}_i(0)+\hat{Q}_ i(1)=\hat{Q}_{i-1}(a_{i-1})$
, for $i=2,\ldots j$, where $j$ is a round at which $P$ was lucky when 
$V$  selected an $a_j$ from $\F$ for which 
$\hat{Q}_j(a_j)=Q_j(a_j)$.
\item Or $V$ computed at the last round 
the value of $Q(a_1,\ldots,a_{3m})$ incorrectly in 
such a way that it turned out to be equal to $\hat{Q}_{3m}(a_{3m})$.
\end{itemize}

For a fixed $j$, the probability that $\hat{Q}_j(a_j)=Q_j(a_j)$,
given that $\hat{Q}_j(z)$ and   $Q_j(z)$ are not equal, is  
at most 
\[
{\mbox{degree}(\hat{Q_i} - Q_i)\over{|\F|}} \leq {6\over{\Theta(m^2)}}   
\]
since the degree of each $Q_i$ is at most $6$ 
(Here we are assuming that 
$V$ rejects when $P$ sends a polynomial whose degree is  more than $6$).
The degree bound on the $Q_i$'s follows from the 
fact that $Q$ is a multi-linear function of  
degree $6$ in each variable independently.
So the probability that  $P$ was lucky at some  $j$,
is at most  $3m(6/\Theta(m^2)) = O(1/m)$. 


To compute $Q(a_1,\ldots,a_{3m})$, the verifier 
 uses the table $T$, which 
might not agree with $A$ in all its entries. 
All what we know from the multi-linearity test 
is that $T$ agrees with $A$ in 99/100 of 
its entries.  So, the  
probability that $V$ computes 
$Q(a_1,\ldots,a_{3m})$ incorrectly, 
is at most 
\[
\mbox{Pr}_{a_1,\ldots,a_{3m}\in \F}[
T(a_{im+1},\ldots,a_{im+m}) \neq A(a_{im+1},\ldots,a_{im+m}) 
\mbox{ for $i=0,1,$ or $2$}]  < {3\over{100}}. 
\]

Therefore for any prover $P$, and any table $T$ that passed 
the multi-linearity test, the 
 probability that $V$ accepts when $FC(\phi,A) \neq 0$ is 
at most $3/100 + O(1/m)<1/25$, for $m$ large enough.  


Finally note that $V$ can compute $Q(a_1,\ldots,a_m)$ by 
accessing the table 
$3$  times, while reading each time $O(\log{m})$ 
bit. Note also that the verifier needs 
$O(m\log{m})$ random bits to select the $a_i$'s, 
and that the prover have to send, in each of the 
the $3m$  rounds,  
$O(\log{m})$ bit to the verifier since   each of the 
polynomials being sent is of degree $\leq 6$. 





\section{ Turning the IP into a PCP}
To turn the IP into a PCP, we store in the probabilistically 
checkable proof $\Pi$,  in addition to the 
table $T$, a huge table $H$ containing 
all the responses of the prover indexed by 
the $O(m\log{m})$ IP verifier random bits 
and the $O(m\log{m})$ random bits 
used in the construction of $FC(\phi,A)$.
In other words,  if $r_1,\ldots,r_s$ are the 
elements of $\F$ 
used in the construction of $FC(\phi,A)$ 
and  if  the IP verifier is at 
round $i$,  then the IP verifier
computes, from     
$(r_1,\ldots,r_s,a_1,\ldots,a_i)$, 
the entry  of $H$ that 
contains the $O(\log{m})$ bits 
corresponding the prover's  response. 
So the  total size of the probabilistically 
checkable proof 
$\Pi$ is $|T|+|H| = 2^{O(\log^{O(1)}{n})} + 2^{O(m\log{m})} = 
2^{O(\log^{O(1)}{n})}$.


The number bits to be read by the PCP verifier 
from the proof is 
 $O(m\log{m} + \log^{O(1)}{n}) = O(\log^{O(1)}{n})$,  where 
the first terms corresponds to the IP protocol 
and the second term corresponds to the multi-linearity test.
Similarly, the number of random bits needed  
by the PCP verifier is  is $O(m\log{m} + 
\log^{O(1)}{n}) = O(\log^{O(1)}{n})$.


Finally, 
\begin{itemize}

\item If $\phi\not\in 3SAT$, then 
for any  probabilistically 
checkable proof 
$\Pi$,  the probability 
that the PCP verifier 
accepts $(\Pi,\phi)$ is bounded by $O(1/m) + 1/25 < 1/2$, where 
the first term is a bound  on the probability 
that $FC(\phi,A) =  0$ is not equivalent to 
the fact that $A$ satisfies all the clauses of $\phi$, 
and the second term is a bound on the probability that 
IP protocol accepts when $FC(\phi,A) \neq 0$.

\item If $\phi\in 3SAT$, then there exits a proof $\Pi$,
   containing a  table that is multi-linear everywhere, 
   and the  responses of an ``honest'' prover,  such 
   that the PCP verifier accepts $(\Pi,\phi)$ w.p. $1$. 
 
\end{itemize}




This proves that 3SAT $\in $ PCP$(\log^{O(1)}{n}, 
\log^{O(1)}{n})$.










\section{A stronger PCP theorem}  

The best $PCP$ theorem know so far 
is 

\begin{theorem}
NP $\subset $ PCP$(\log{n},1).$
\end{theorem}

The size of the corresponding probabilistically 
checkable proof is $n^{1+\epsilon}$, for any $\epsilon>0$.
The proof of this theorem is very complicated and we don't 
know of any simple one. 


This result is 
considered a landmark in  
complexity theory.
We will see in the next lecture how it can 
be applied   to establish the hardness of 
approximating various optimization problems. 












\end{document}



