\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}