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