\documentclass[10pt]{article} %\usepackage{preamble} \input{preamble.tex} %\input{fullpage.sty} \usepackage{amsmath, amssymb, amsfonts} \usepackage{fullpage} \usepackage{color} \usepackage{graphicx} %\usepackage{bbm} %\usepackage{url} %\usepackage{citesort,epsfig,enumerate} % complexity classes \newcommand{\prRP}{\mathrm{prRP}} \newcommand{\RP}{\mathrm{RP}} \newcommand{\prBPP}{\mathrm{prBPP}} \newcommand{\BPP}{\mathrm{BPP}} \newcommand{\prP}{\mathrm{prP}} \newcommand{\clsP}{\mathrm{P}} \newcommand{\NP}{\mathrm{NP}} \newcommand{\IP}{\mathrm{IP}} \newcommand{\PSPACE}{\mathrm{PSPACE}} \newcommand{\Ppoly}{\mathrm{P}/\mathrm{poly}} \newcommand{\CSIZE}[1]{\mathrm{CSIZE}\left(#1\right)} \newcommand{\PH}{\mathrm{PH}} \newcommand{\PCP}{\mathrm{PCP}} \newcommand{\MOD}{\mathrm{MOD}} \newcommand{\ACC}{\mathrm{ACC}} % Turing Machines \newcommand{\acc}[2]{#1\text{~accepts~}#2} \newcommand{\rej}[2]{#1\text{~accepts~}#2} %\newcommand{\enc}[1]{\langle #1\rangle} % Math \newcommand{\st}{\text{~such that~}} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\SAT}{\mathrm{SAT}} \newcommand{\pilin}{\pi_{\text{lin}}} \newcommand{\remove}[1]{} \begin{document} \lecture{19}{April, 23, 2007}{Madhu Sudan}{Kuen-Bang Hou and Ning Xie} Today we will continue our study of PCP's and show an exponentially long $\PCP$ for $\SAT$. \section{Review of last lecture: two views of $\PCP$} First we review some results covered in last lecture: there are two different views to look at $\PCP$ systems. The first view is to treat PCP as a proof system having the following special property. There exists a probabilistic polynomial time proof verifier $V$ for $L$ such that: %% \begin{align*} %% x \in L &\Longrightarrow \exists \pi \st \Pr{[V^{\pi} (x,R)]} = 1 \\ %% x \notin L &\Longrightarrow \forall \pi \Pr{[V^{\pi} (x,R)]} \leq 1-\epsilon. %% \end{align*} \begin{itemize} \item $x \in L \Rightarrow \exists \pi \text{~s.t.~} \Pr_{R}{[V^{\pi} (x,R)]} = 1$ \item $x \notin L \Rightarrow \forall \pi ~\Pr_{R}{[V^{\pi} (x,R)]} \leq 1-\epsilon,$ \end{itemize} where $|\pi|$ should be small, $\epsilon > 0$ is a constant and \#queries into $\pi$ should be small (e.g. $O(1)$). \begin{figure}[htbp] \center \input{lect19-pcp.pstex_t} \caption{Relationship among the proof $\pi$, the input $x$, the random coin tosses $R$ and the verifier $V$}\label{fig:pcp} \end{figure} The second view is to think PCP as a reduction from $L$ to the problem of Generalized Graph $k$-coloring such that: \begin{itemize} \item $x \in L \Longrightarrow G_{x}~\text{is $k$-colorable}$; \item $x \notin L \Longrightarrow \forall \text{$k$-coloring of $G_{x}$, at least $\epsilon$ fraction of the edges are invalid coloring in $G_{x}$}.$ \end{itemize} Note that if $|\pi|$ is polynomially bounded, these two views are equivalent. However, today we are going to see an exponentially long proof verifiable by $O(1)$ queries. This is trivial in View 2 but is highly non-trivial in View 1. \remove{ The proof might be of length $2^{{|x|}^{O(1)}}$ % O(1) % |x| % 2 % % [============================================] % ^ ^ ^ % \----------+---/---/ % (V) % [x]------/ \---- [R] \subsection{$\PCP$ View $1$} Probabilistic verifier of proofs % % % [============== Pi ===================] % ^ ^ ^ % \----------+---/---/ % (V) % [x]------/ \---- [R] \begin{enumerate} \item $x\in L$ then $\exists \pi \st \Pr{V^{\pi} (x,R)} = 1$ \item $x\notin L$ then $\forall \pi \st \Pr{V^{\pi} (x,R)} \leq 1-\epsilon $ \end{enumerate} where $|\pi|$ should be small, $\epsilon > 0$, \#queries into $\pi$ hold be small ($O(1)$). \subsection{$\PCP$ view $2$} Reduction: $L \leq $ Generalized Graph $k$-coloring \begin{enumerate} \item $x \in L$ then $G_x$ should be validly $k$-colorable where $G_x$ includes graph for each edge description of valid coloring. \item $x \notin L$ then $\forall k$-coloring, at least $\epsilon$ fraction of edges are invalidly colored in $G_x$ \end{enumerate} If the $\pi$ is polynomially bound, then two views are equivalent. But if $\pi$ is not, then the reduction is not useful because the size of $G_x$ can be exponentially large! However, it's a step toward $\PCP$ theorem. We'll allow exponentially long proofs and polynomially many coins today. } \section{PCP system for Quadratic-$\SAT$} \subsection{Quadratic-$\SAT$} \newcommand{\GF}[1]{\mathrm{GF}(#1)} \begin{definition}[Quadratic-$\SAT$] Consider the following decision problem, which is a variant of $\SAT$: \begin{align*} &\bf{Given}: \text{$x_1,\ldots, x_n \in \GF{2}$ and a set of $m$ degree-2 polynomials $P_1,\cdots, P_m$ in $n$ variable;}\\ &\bf{Question}: \text{Does there exist an $\vec{a}=(a_1,\dots,a_n)\in \GF{2}^n$ such that for all $j \in \{1,\dots,m\}$ $P_{j}(\vec{a}) = 0$?} \end{align*} \end{definition} It is easy to see that Quadratic-$\SAT \in \NP$. It can also be checked that Quadratic-$\SAT$ is NP-hard\footnote{ Note that if we map $1$ to \textsc{True} and map $0$ to \textsc{False}, then the AND gate and OR gate can be expressed by quadratic polynomials over $\GF{2}$ as $\text{AND}(x,y)=x\cdot y$ and $\text{OR}(x,y)=x+y+x\cdot y$. Consider the following reduction from 3SAT to Quadratic-$\SAT$. Let $\psi \in 3\text{SAT}$. For each clause $c_i = (x_i\vee y_i\vee z_i)$ in $\psi$ (note that the complement of $x$ is mapped to $(1-x)$ and this will not increase the degree), build two polynomials $P_{2i}, P_{2i+1}$ as $P_{2i} = x_i + y_i + x_i y_i+w_i$ and $P_{2i+1} = z_i+w_i+z_i w_i+1$. This construction introduces at most a polynomial number of new variables and it is easily seen that $P_{2i} = P_{2i+1} = 0$ if and only if $c_i = (x_i\vee y_i\vee z_i) = \textsc{True}$.}. Therefore it is NP-complete. In the following we will describe an exponentially long PCP for Quadratic-$\SAT$. The key ideas will be arithmetization of $\SAT$ and exploiting some nice properties of linear functions (low-degree polynomials). \subsection{What is the proof} Let $Q$ be a degree-$2$ polynomials in $n$ variables over $\GF{2}$. Then $Q(x_1,\dots,x_n) = \sum_{1\leq i,j\leq n} q_{i,j} x_i x_j + q_0$. Since we are working over $\GF{2}$, $x^2=x$ and this general form includes all the linear functions as well. Note that a quadratic polynomial over $\GF{2}$ is completely determined by the set of coefficients: $Q \equiv (\{q_{i,j}\}, q_0)$. It follows that the total number of degree-$2$ polynomials in $n$ variables over $\GF{2}$ is $2^{O(n^2)}$. Now our proof $\pi$ for the PCP system is simply the list of the evaluations of a satisfying assignment $\vec{a}$ at all quadratic polynomials. Therefore $|\pi|=2^{O(n^2)}$. %% Hope: $\pi[Q] = Q(\vec{a})$ for a satisfying assignment $a$ where $\pi$ is of length $2^{n^2}$ \subsection{What should be checked for the proof} There are two issues to address. First, $\pi$ may not equal to $\{Q(\vec{a})\}$ for any $\vec{a}$. Second, $\vec{a}$ may not be a satisfying assignment. \begin{itemize} \item {\bf Syntactic Question:} Does there exist an $\vec{a} \st \pi[Q] = Q(\vec{a}) \text{~for all~} Q$? Since the number of quadratic polynomials is exponentially large and an invalid proof may be formed by flip only one bit from a valid proof, this is not possible to check in polynomial time. Instead, we relax the question to: Does there exist an $\vec{a} \st \Pr_Q{[\pi[Q] = Q(\vec{a})]} \geq 1-\delta$? Note that even after the relaxation there can be only one $\vec{a}$ that passes the check provided that $\delta$ is small enough. \item {\bf Semantic Question:} Is $P_1(\vec{a}) = P_2(\vec{a}) =\dots =P_m(\vec{a}) = 0$ ? \end{itemize} We will study the semantic question first since it is easier and then come back to handle the syntactic question later. \subsection{Semantic test} Now we assume that the proof $\pi$ already passes the Syntactic test; i.e., we are given a table $\pi$ which encodes the evaluation of some $\vec{a}$ at all the quadratic polynomials such that for at least $1-\delta$ fraction of the points, $\pi[Q]=Q(\vec{a})$. We want to test if $\vec{a}$ is a satisfying assignment for Quadratic-SAT by probing the table only at a constant number of locations. We start with the easiest case: Suppose that there is only one polynomial $P_1$ (i.e. $m=1$). Note that we can not just read $\pi[P_1]$ since that point may be in the corrupted portion of the proof. Instead, we use the idea of random self-reducibility introduced before: Pick another polynomial $Q$ at random, compute $\tilde \pi[P_1] \eqdef \pi[P_1 +Q]- \pi[Q]$ and check if it is $0$. The key point here is that, for any fixed $P_1$, if $Q$ is a random quadratic polynomial, then so is $P_1+Q$. Therefore, $\Pr_{Q}[\pi[Q] \neq Q(\vec{a})] \leq \delta$ and $\Pr_{Q}[\pi[P_{1}+Q] \neq P_{1}(\vec{a})+Q(\vec{a})] \leq \delta$, applying union bound gives $\Pr_{Q}[\tilde \pi[P_1] \neq P_{1}(\vec{a})] \leq 2\delta$. For general $m$, we can not repeat the above test for every $P_{i}$, since we are only allowed to query constant bits. We will use the idea of approximating OR gates by probabilistic low-degree polynomials in Razborov-Smolensky's proof of circuit lower bound for PARITY. Here our task is to check if $\bigwedge^m_{j=1} (P_j(\vec{a}) = 0)$. \begin{enumerate} \item pick $\alpha_1, \ldots, \alpha_m \in \GF{2}$ uniformly at random; \item check if $P_\alpha (x_1,\dots,x_n) \eqdef \sum^m_{j=1} \alpha_j P_j(x_1,\dots,x_n)$ evaluates to $0$ at point $\vec{a}$. \end{enumerate} \paragraph{Analysis:} Note that $P_\alpha$ is a degree-$2$ polynomial in $x_1, \ldots, x_n$. It is easy to see that, if for all $j \in [m]$ $P_{j}(\vec{a})=0$, then $P_\alpha(\vec{a}) = 0$. On the other hand, if there exists a $j$ such that $P_{j}(\vec{a}) \neq 0$, then $P_\alpha$ is a non-vanishing multilinear polynomial in $\alpha_1, \ldots, \alpha_m$. By Schwartz-Zippel Lemma, $\Pr_{\alpha_1, \ldots, \alpha_m}[P_{\alpha}(\vec{a}) \neq 0] \geq \frac{1}{2}$. Now we combine these two ideas together and get the following Semantic Test: \begin{center} \fbox{ \begin{minipage}[t]{10cm} %%\begin{tabbing} \textbf{Semantic Test:} Is $P_1(\vec{a}) = P_2(\vec{a}) =\dots =P_m(\vec{a}) = 0$? \begin{itemize} \item pick $\alpha_1, \ldots, \alpha_m \in \GF{2}$ uniformly at random \item set $P_{\alpha} = \sum_{j=1}^{m} \alpha_j P_j$ \item pick $Q$ randomly from the set of quadratic polynomials \item accept if $\pi[Q+P_\alpha] = \pi[Q]$ \end{itemize} %%\end{tabbing} \end{minipage} } \end{center} %% $\alpha_1 \dots \alpha_m \gets$ random, $Q \gets$ random, set $P_x = \sum \alpha_j P_j$, and ask if $\pi[Q+P_\alpha] = \pi[Q]$? \subsection{Syntactic test} Now we come back to the first test. Recall that our task is, given a proof $\pi$, to test if there exists an $\vec{a}$ such that $\Pr_{Q}[\pi[Q]=Q(\vec{a})]\leq \delta$. The idea is to look for structural properties of such a proof $\pi$ and test for them. Observe that quadratic function evaluation satisfies the linearity property: $\pi[Q_1]+\pi[Q_2]=\pi[Q_1 + Q_2]$ for all $Q_1$ and $Q_2$. Conversely, for any $\tilde \pi$ satisfying that \[ \forall Q_1, Q_2, \tilde\pi[Q_1] + \tilde\pi[Q_2] = \tilde\pi[Q_1 + Q_2], \] there exist $\{b_{i,j}\}_{i=1,j=1}^{n,n}$ and $b_0$ such that for all $Q = (\{q_{i,j}\}, q_0)$, $\tilde \pi[Q] = \sum q_{i,j} b_{i,j} + q_0 b_0$. Therefore we break the Syntactic Test into two parts: First we test if the proof $\pi$ passes the linearity test, then we check if \begin{itemize} \item $b_{i,j} = a_i a_j$ for all $i$ and $j$, and \item $b_0 = 1$. \end{itemize} \remove{ We want to test the existence of $\tilde\pi$ close to $\pi$ satisfying following properties. Note that we use $\tilde\pi$ instead of $\pi$ because we can only make sure the existence of another proof $\tilde\pi$ which has the desired properties. For a faithful prover, it can simply offer the proof $\tilde\pi$ we'll show. \begin{itemize} \item There a proof $\tilde\pi$ such that $\Pr_Q{[\tilde\pi[Q] \neq \pi[Q]]}$ is small, and \item $\forall Q_1, Q_2, \tilde\pi[Q_1] + \tilde\pi[Q_2] = \tilde\pi[Q_1 + Q_2] $, and \item $\exists \{b_{i,j}\}_{i,j}, b_0$ s.t. $\forall Q = \{\{q_{i,j}\}, q_0\}$, $\tilde \pi[Q] = \sum q_{i,j} b_{i,j} + q_0 b_0$ where \begin{itemize} \item $b_{i,j} = a_i a_j$ and \item $b_0 = 1$. \end{itemize} \end{itemize} The first one says that $\pi$ is very close to a nice prove $\tilde\pi$. The second one guarantees the linearity of $\tilde\pi$, which implies that $\pi[Q]$ is a linear function on some variables, say $b$'s. (i.e., $\tilde\pi[Q] = \sum q_{i,j} b_{i,j} + q_0b_0$) The last one makes sure that $b$'s are really computed from $\vec{a}$. It's easy to see that the syntactic test can be broken down to these tests, and if such $\tilde\pi$ exists, then $\pi$ is really computed from some assignment $\vec a$ for most parts. Now we focus on the first two statements. } \subsubsection{The First Part of the Syntactic Test} We've already used the idea $Q_1(a) + Q_2(a) = (Q_1+Q_2)(a)$ in the previous test. Here we are going to use that idea again. %% This equation suggests the following test: Our linearity test is simply the following: Pick $Q_1$, $Q_2$ at random and check if $\pi[Q_1] + \pi[Q_2] = \pi[Q_1+Q_2]$. If the proof $\pi$ passes the test, however, we can only conclude that $\Pr_{Q_1,Q_2} [\pi[Q_1] + \pi[Q_2] = \pi[Q_1 + Q_2]]$ is high, which is far from the statement that \emph{for all} $Q_1, Q_2$, $\pi[Q_1] + \pi[Q_2] =\pi[Q_1 + Q_2]$. Fortunately, this property guarantees that there is another proof $\tilde\pi$ which is linear (i.e. for all $Q_1, Q_2$, $\tilde\pi[Q_1] + \tilde\pi[Q_2] = \tilde\pi[Q_1 + Q_2]$) and is very close to $\pi$. The existence of such $\tilde \pi$ is stated formally in the following remarkable theorem of Blum, Luby and Rubinfeld: \begin{theorem}[BLR Theorem] If $\Pr{[\pi[Q_1] + \pi[Q_2] \neq \pi[Q_1+Q_2]]} \leq \delta$ then \begin{enumerate} \item $\exists \tilde \pi \st \forall Q_1,Q_2: \tilde \pi[Q_1] + \tilde \pi[Q_2] = \tilde\pi [Q_1 + Q_2]$ and \item $\Pr_Q[\pi[Q] \neq \tilde\pi[Q]] \leq 2\delta$ \end{enumerate} provided that $\delta < 2/9$. \end{theorem} We will not prove this theorem here. Interested readers are referred to the two courses taught by Prof. Rubinfeld: 6.895 Randomness and Computation and 6.896 Sublinear Time Algorithms. The proof is in \cite{BLR90}. The constant $2/9$ is important because we're only allowed to use a constant number of queries, and the soundness bound $2/9$ is achievable by a constant number of queries. %%So the first part can be carried out by first testing if $\Pr{[\pi[Q_1] + \pi[Q_2] \neq \pi[Q_1+Q_2]]}$ is small. \subsubsection{The Second Part of the Syntactic Test} It remains to test the following: Are $b$'s generated from some assignment $\vec{a}$ such $b_0 = 1$ and $b_{i,j} = a_i a_j$ if we write the value of $\tilde\pi[Q]$ as $\sum q_{i,j} b_{i,j} + q_0 b_0$? Keep in mind that we are only given a proof $\pi$ which may disagree with $\tilde \pi$ on $2\delta$ fraction of the points. \begin{enumerate} \item Is $b_0 = 1$? Define the polynomial $\bar 1$ to be $\{\{0\},1\}$, then $\bar 1(a_1,\ldots,a_n) = b_0$. Using the same idea we used before, we pick a random $Q$ and test if $\pi[Q + \bar 1] - \pi[Q] = 1$. \item Is $b_{i,j} = a_i a_j$ for every $i$, $j$? This is equivalent to testing if $\vec b = \{b\}_{i,j} = \vec{a} \vec{a}^T$. First we state a technical claim. \begin{claim} Let $\vec{b}\in \GF{2}^{n \times n}$ and let $\vec{a} \in \GF{2}^{n}$. Let $u, v \in \GF{2}^{n}$. If $\vec{b} \neq \vec{a}\vec{a}^{T}$, then \[ \Pr_{u,v}[u^{T}\vec{b}v \neq u^{T}\vec{a}\vec{a}^{T} v]\geq 1/4. \] \end{claim} \begin{proof} Left as an exercise to the reader. \end{proof} This claim suggests the following test: Pick $u$ and $v$ at random and check if $u^T \vec{b} v = u^T \vec{a} \vec{a}^T v$. The left hand side can be read from $\pi[Q_{u,v}]$, where $Q_{u,v}=(q_{i,j},q_0)$, $q_{i,j} = u_iv_j$ and $q_0 = 0$. But how do we compute $v^T a$ and $u^T a$? Instead, we ask the prover to provide the answers and we check them! Specifically, the prover provides an appendix $\pilin$ where $\pilin[v] = v^T \vec{a}$ for each vector $v$. Note that this is just the evaluation of all linear functions at point $\vec{a}$. Now assuming the appendix is correct, the following test will work: \begin{enumerate} \item pick random vectors $u$, $v$ and random quadratic polynomial $Q$ \item test if $\pi[Q + Q_{u,v}] - \pi[Q] = \pilin[u] \cdot \pilin[v]$ \end{enumerate} \end{enumerate} However, we have to make sure that the appendix is correct. As before, this can be done by picking $u$ and $v$ at random and testing if \[ \pilin[u] + \pilin[v] = \pilin[u + v]. \] \subsection{Summary} Now we have completed the description a PCP system for Quadratic-SAT. The prover provides $\pi$ and $\pilin$, which are evaluations of the set of quadratic polynomials and the set of linear functions at a satisfying assignment $\vec{a}$. The verifier performs the following tests and accepts only if all the tests pass. \begin{enumerate} \item Test 1: Linearity of $\pilin$ \begin{itemize} \item $\pilin[u] + \pilin[v] = \pilin[u+v]$? %% Reject if not. \end{itemize} \item Test 2: Quadraticity of $\pi$ \begin{enumerate} \item $\pi[Q_1] + \pi[Q_2] = \pi[Q_1 + Q_2]$? %% Reject if not. \item $\pi[Q + Q_{u,v}] - \pi[Q] = \pilin[u] \cdot \pilin[v]$? %% Reject if not. \item $\pi[Q+\bar{1}] - \pi[Q] = 1$? \end{enumerate} \item Semantic Test \begin{itemize} \item pick $\{\alpha_1, \ldots, \alpha_m \}$ at random and set $P_\alpha = \sum_{j=1}^{m} \alpha_j P_j$ \item $Q \gets $ random \item $\pi[Q + P_\alpha] = \pi[Q]$? %% Reject if not. \end{itemize} \end{enumerate} \paragraph{Analysis:} \begin{itemize} \item The verifier makes $14=O(1)$ number of queries to the proof \item $(\exists \vec{a} \text{~s.t.~} P_{j}(\vec{a})=0 ~\forall ~ j) \Rightarrow \exists \pi, \pilin \text{~s.t.~} \Pr[\text{Verifier accepts}]=1$ \item $\Pr[\text{Verifier accepts}] \geq 0.99 \Rightarrow \exists \vec{a} \text{~s.t.~} P_1(\vec{a})= \cdots = P_m(\vec{a})=0$ \end{itemize} \subsection{Exercise for the next lecture} We would like to have a reduction which has the following property: $\exists \tau > 0 \st \forall k$ Generalized $k$-coloring $\leq$ Generalized $3$-coloring such that \begin{itemize} \item $G_x$ is $k$-colorable $\to$ $G_x'$ is $3$-colorable \item $G_x$ is $\epsilon$-far from $k$-colorable $\to$ $G'_x$ is $\epsilon\cdot\tau$-far from $3$-colorable. \end{itemize} Note that this is different from the classical Garey-Johnson type reduction, in which $\tau$ is in general dependent on $k$. \bibliographystyle{alpha} \bibliography{lect19} \end{document}