%% LyX 1.5.4 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[oneside,english]{amsart}
\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\usepackage{nicefrac}
\usepackage{graphicx}
\usepackage{amssymb}

\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\numberwithin{equation}{section} %% Comment out for sequentially-numbered
\numberwithin{figure}{section} %% Comment out for sequentially-numbered
  \theoremstyle{plain}
  \newtheorem{thm}{Theorem}[section]
  \theoremstyle{definition}
  \newtheorem{defn}[thm]{Definition}
  \theoremstyle{plain}
  \newtheorem{lem}[thm]{Lemma}
  \theoremstyle{plain}
  \newtheorem{algorithm}[thm]{Algorithm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\input{preamble.tex}

\lecture{19}{April 15, 2009}{Madhu Sudan}{Alex Arkhipov}

\usepackage{babel}
\makeatother

\begin{document}

\section{Review of Last Class}

Last class we gave a formulation of Probabilistically Checkable Proofs
as a coloring of a graph that satisfies certain constraints.

\begin{defn}
The \textit{graph $k$-coloring problem} is as follows:
\begin{quote}
Given a graph $G=\left(E,V\right)$, does there exist a coloring $\chi:V\rightarrow\left\{ 1,2,\dots,k\right\} $
such that for each $(u,v)\in E$, $\chi(u)\neq\chi(v)$?
\end{quote}
\end{defn}
In generalized graph coloring, each edge restricts the coloring of
its endpoints by an arbitary relation, described by an admissibility
function $\Pi$.

\begin{defn}
The generalized \textit{$k$-coloring problem} is as follows:
\begin{quote}
Given a graph $G=\left(E,V,\Pi\right)$, which includes map $\Pi:E\times\left\{ 1,2,\dots,k\right\} \times\left\{ 1,2,\dots,k\right\} \rightarrow\left\{ 0,1\right\} $,
does there exist a coloring $\chi:V\rightarrow\left\{ 1,2,\dots,k\right\} $
such that for each $e=(u,v)\in E$, $\Pi\left(e,\chi\left(u\right),\chi\left(v\right)\right)=1$?
\end{quote}
\end{defn}
In a coloring $\chi$, we say an edge $e=(u,v)$ is \textit{invalid
}if it does not satisfy the constraint $\Pi\left(e,\chi\left(u\right),\chi\left(v\right)\right)=1$.
The unsatisfiability UNSAT$(G,\chi)$ is fraction of invalid edges
in $G$, and the unsatisfiability UNSAT$(G)$ of a graph is the minimum
UNSAT$(G,\chi)$ over all colorings $\chi$.

Recall the Lemma that we wished to prove that would allow us to reduce
the number of colors:

\begin{lem}
\label{lem:colorreduction}There exists a $k$ and $\delta>0$, so
that for any $K$, there is a reduction function $f$ from $K$-coloring
instances to $k$-coloring instances so that for any $G$ and $\tilde{G}=f\left(G\right)$,
\begin{itemize}
\item If $\mbox{UNSAT}(G)=0$, then $\mbox{UNSAT}(\tilde{G})=0$.
\item $\mbox{UNSAT}(\tilde{G})\geq\delta\mbox{UNSAT}(G)$
\end{itemize}
\end{lem}
We'll first see look at a naive attempt to perform this reduction,
and see how it can lead to unsatisfiability falling by more than a
constant factor $\delta$.


\subsection{Attempt at reduction from $K$-coloring to $3$-coloring}

To illustrate the obstacle to showing Lemma \ref{lem:colorreduction},
we'll sketch a linear time reduction for standard $K$-coloring to
standard $k$-coloring, with $k=3$. We'll convert $K$-coloring instance
$G$ to a $3$-coloring instance $\tilde{G}$ by replacing each edge
of $G$ with a gadget of $\tilde{G}$ that encodes the same restriction.
However, we'll find that if $\mbox{UNSAT}\left(G\right)=\varepsilon$,
then $\mbox{UNSAT}\left(\tilde{G}\right)\leq\frac{\varepsilon}{K}$,
and thus cannot satisfy $\mbox{UNSAT}(\tilde{G})\geq\delta\mbox{UNSAT}(G)$
for any constant $\delta$.


\subsubsection{Construction of $\tilde{G}$}

Make three special nodes $\left\{ r,g,b\right\} $ and connect them
with edges, so that they must be different colors which we'll label
red, green, and blue, which we will also call the three possible colors
of the nodes. We may restrict the possible colors of a node in $\tilde{G}$
by connecting it to each of $\left\{ r,g,b\right\} $ we want to exclude.

For each node $u\in G$, make $K+1$ nodes $u_{0},\dots u_{K}$ in
$\tilde{G}$. Restrict them to be each red or green (by connecting
each by an edge to the blue node), and furthermore restrict $u_{0}$
to be red and $u_{K}$ to be green. Then, in any coloring of $\tilde{G}$,
there is some first node $u_{j}$ that marks a switch from red to
green; i.e. the first $i\in\left\{ 1,\dots,K\right\} $ so that $u_{j-1}$
is red and $u_{j}$ is green. (We may assume that $u_{i}$ is red
for $i<j$ and green for $i\geq j$, as we'll see that allowing additional
{}``switches'' won't give any advantage in coloring the graph).
To such a coloring of the $u_{i}$ nodes in $G$, we associate the
node $u\in G$ being colored with color $i$.

%
\begin{figure}
\includegraphics[scale=0.45]{\string"Graph vertex\string".eps}

\caption{The conversion of a vertex of $G$ to one of $\tilde{G}$. The vertices
are marked with their possible colors.}



\end{figure}


We need to enforce the restriction that for each edge $(u,v)\in G$,
$u$ and $v$ have different colors. Correspondingly in $\tilde{G}$,
we put in gadgets to ensure that $u$ and $v$ don't both switch colors
at the same value, that there for no $i\in\left\{ 1,\dots,K\right\} $
so that $u_{i-1}$ is red and $u_{i}$ green, and also $v_{i-1}$
red and $v_{i}$ is green. To do so, for each $i$, we put in a gadget
with two additional nodes $x_{uvi}$ and $y_{uvi}$, which are edge-connected
to each other and to $u_{i-1}$ and $u_{i}$, and to $v_{i-1}$ and
$v_{i}$, respectively.

If both $u$ and $v$ have color $j$, then both the added node $x_{uv}$
and $y_{uv}$ can't be red or green, and are forced to be blue, which
is disallowed. In any other case, valid colorings exist for the two
added nodes. So, we have encoded the restriction for the edge $\left(u,v\right)\in G$.

%
\begin{figure}
\includegraphics[scale=0.4]{Test/Picture1}

\caption{Each edge of $G$ is repaced by a gadget in $\tilde{G}$ that enforces
the constraint the $u$ and $v$ are different colors by enforcing
the fact that the sequences of colors $u_{i}$ and $v_{i}$ cannot
switch at the same point.}

\end{figure}



\subsubsection{Analysis of Reduction}

From the construction of $\tilde{G}$, it's easy to see that $\tilde{G}$
is $3$-colorable if and only $G$ is $K$-colorable. How does the
unsatisfiability of $G$ compare to that of $\tilde{G}$?

Suppose the best $K$-coloring of $\tilde{G}$ fails on $d$ edges,
so that UNSAT$\left(G\right)=d/\left|G\right|$ (where the size of
a graph is its number of edges). Then, for each invalid edge $\left(u,v\right)\in G$,
say with $\chi(u)=\chi(v)=i$, we may color the $\left(u,v\right)$
edge gadget in $\tilde{G}$ so that is valid for all but one edge
by allowing both $x_{uvi}$ and $y_{uvi}$ to be blue. So, $\tilde{G}$
fails on only $d$ edges and UNSAT$\left(\tilde{G}\right)\leq d/\left|\tilde{G}\right|$.
(It is possible that UNSAT$(\tilde{G)}$ is smaller, if multiple invalid
edges in $G$ share a vertex $u$, illegally coloring $u_{0},\dots,u_{K}\in\tilde{G}$
gives only one invalid edge in $\tilde{G}$.) Since $\left|\tilde{G}\right|/\left|G\right|=\Theta(K)$,
$\mbox{UNSAT}(\tilde{G})=O\left(\frac{1}{K}\right)\mbox{UNSAT}(G)$.
So, we fail to produce an at most constant reduction of unsatisfiability.

In the hopes of finding a better reduction, we look at a way to construct
exponentially long PCP's that we will use to create a better $K$-coloring
to $k$-coloring reduction.


\section{Quadratic Equation Solvability}

We give a scheme for giving a Probabilistically Checkable Proof of
an NP-complete problem that is exponentially-sized and requires a
constant number of queries. This scheme is due to Arora, Lund, Motwani,
Sudan, and Szegedy.


\subsection{Problem Definition}

The Quadratic Equation Solvability Problem is like SAT, in that it
asks whether a given formula, consisting of the AND of $m$ clauses,
is satisfiable. except each of these clauses may be an arbitrary second-degree
polynomial in the variables $x_{1},\dots,x_{n}$.

\begin{defn}
The \textit{Quadratic Equation Solvability Problem} takes as input
a formula $\phi$ of $n$ Boolean variables $x_{1},\dots,x_{n}$ that
is the AND of $m$ clauses that are degree-2 polynomials $p_{1},\dots,p_{m}$
of the variables $x_{1},\dots,x_{n}$ over $\mathbb{Z}_{2}$, and
asks whether $\phi$ has a satisfying assignment $\bar{a}$ (so that
$p_{i}(\bar{a})=0$ for each $i$).
\end{defn}
Since in a circuit, we may express the relations given by a AND, OR,
and NOT gates by a quadratic expressions, this problem is at least
as hard a circuit-SAT, and thus NP-hard. It is NP hard, since it's
easy to verify a satisfying assignment.


\subsection{PCP Scheme}

Let $Z_{1}$ be sets of all homogenous linear polynomials in $n$
variables $x_{1}.\dots,x_{n}$, and let $Z_{2}$ be all homogenous
quadratic polynomials, respectively. The PCP will contain information
about a satisfying assignment of the QES formula in the form of two
tables: $T_{1}$ and $T_{2}$, of size $2^{n}$ and $2^{n^{2}}$,
that are claimed to be list the values of $Z_{1}$ and $Z_{2}$, respectively,
on some single satisfying assignment $\bar{a}$. However, since the
prover may cheat and put any values in the tables, to check that the
proof is valid, it is up to the verifier to see that there exists
an $\bar{a}$ so that the following three conditions hold:

\begin{enumerate}
\item For each linear polynomial $L$, $T_{1}\left(L\right)=L\left(\bar{a}\right)$.
\item For each quadratic polynomial $Q$, $Q_{1}\left(L\right)=Q\left(\bar{a}\right)$ 
\item For each of the polynomial clauses $P_{i}$, $P_{i}\left(\bar{a}\right)=0$.
\end{enumerate}
The first two check the validity of the tables, and then the third
trusts the values in the tables to be valid (i.e. to contain the value
of the state polynomial as $\bar{a}$) in order to check that the
assignment claimed is satisfying. 

Since we, as the verifier, may only make a constant number of queries,
we cannot confirm these conditions with certainty. So, we need to
make a scheme so that if the QES formula cannot be satisfied, an adversary
making the tables is forced to commit to a large number of discrepancies
that we can catch.

We will show that the following verification algorithm works:

\begin{algorithm}
We verification the PCP in three verification steps, corresponding
to the three properties given above:
\begin{enumerate}
\item Pick $L_{1},L_{2}\in Z_{1}$ at random, and check that \[
T_{1}\left(L_{1}\right)+T_{1}\left(L_{2}\right)=T_{1}\left(L_{1}+L_{2}\right)\]
 (all computations are modulo 2).
\item $\,$

\begin{enumerate}
\item Pick $Q_{1},Q_{2}\in Z_{2}$ at random, and check that\[
T_{2}\left(Q_{1}\right)+T_{2}\left(Q_{2}\right)=T_{2}\left(Q_{1}+Q_{2}\right)\]
. 
\item Pick $L_{1},L_{2}\in Z_{1}$ and $S\in Z_{2}$ at random, and check
that \[
T_{2}\left(S+L_{1}L_{2}\right)=T_{2}\left(S\right)+T_{1}\left(L_{1}\right)T_{1}\left(L_{2}\right)\]
.
\end{enumerate}
\item Pick $r\in\left\{ 0,1\right\} ^{m}$ at random and let $A_{r}=\sum r_{j}P_{j}$.
Write \[
A_{r}=Q_{r}+L_{r}+C_{r}\]
with $Q_{r}\in Z_{2}$, $L_{r}\in Z_{1}$, and $C$ constant. Pick
$S\in Z_{2}$ at random and check that \[
T_{2}\left(Q_{r}+S\right)-T_{2}\left(S\right)+T_{1}\left(L_{r}\right)+C_{r}=0\]
. 
\end{enumerate}
If any of these checks rejects, then reject. Otherwise, accept.
\end{algorithm}
This scheme uses a constant number of queries (specifically ten).

We would like to show the following.

\begin{thm}
The given verification scheme $V$ has the following properties:
\begin{itemize}
\item If $\phi$ is satisfiable, then for tables $T_{1}$ and $T_{2}$ as
described, then $V$ returns $YES$.
\item If $\phi$ is not satisfiable, then for any tables $T_{1}$ and $T_{2}$,
then $V$ returns $YES$ with probability $F\leq\frac{8}{9}$.
\end{itemize}
\end{thm}
It should be easy to see that the first part is true, since giving
tables $T_{1}\left(L\right)=L\left(\bar{a}\right)$, $Q_{1}\left(L\right)=Q\left(\bar{a}\right)$
for a valid satisfying assignment $\bar{a}$ will pass the three checks
regardless of the random choices made.

For the remainder of the section, will put a bound on $F$, the probability
that we are falsely led to accept when $\phi$ is not satisfiable.

Define $\delta_{1}$ and $\delta_{2}$ be the fraction of entries
in $T_{1}$ for which $T_{1}\left(L\right)\neq L\left(\bar{a}\right)$
(we'll call these invalid entries), minimized over all satisfying
assignments $\bar{a}$, and let $\delta_{2}$ be fraction of invalid
entries of $T_{2}$.\[
\delta_{1}=\min_{\bar{a}}\left[\Pr_{L}\left[T_{1}\left(L\right)\neq L\left(\bar{a}\right)\right]\right]\]


\[
\delta_{2}=\min_{\bar{a}}\left[\Pr_{Q}\left[T_{2}\left(Q\right)\neq Q\left(\bar{a}\right)\right]\right]\]
We will also use another discrepancy measure that says how nonlinear
$T_{2}$ is

\[
\delta_{3}=\min_{\left(c_{ij}\right)}\left[\Pr_{L_{1},L_{2}}\left[T_{2}\left(c_{11},\dots,c_{nn}\right)\neq\sum_{i,j}c_{ij}b_{ij}\right]\right]\]


Define $F_{1}$, $F_{2a}$, $F_{2b}$, and $F_{3}$ to be maximum
probability that verifications steps $(1)$, $(2a)$, $(2b)$, and
$(3)$, respectively, accept, given that $\ \phi$ has no satisfying
assignment. Then, $F\leq F_{1}F_{2}F_{3}$. We'll show that $F\leq\nicefrac{8}{9}$
by bounding $F_{1}$, $F_{2}$, and $F_{3}$ in terms of $\delta_{1}$,
$\delta_{2}$, and $\delta_{3}$.

\begin{lem}
The probability $F_{1}$ that verification step $(1)$ accepts has
$F_{1}\leq1-\frac{2}{9}\delta_{1}$.
\end{lem}
\begin{proof}
For any two polynomials $L_{1}$ and $L_{2}$, it must be true that
$\left(L_{1}+L_{2}\right)\left(\bar{a}\right)=L_{1}\left(\bar{a}\right)+L_{2}\left(\bar{a}\right)$
(taken modulo 2). In the first verification step, we check that $T_{1}$
respects this property on a single instance of two linear functions.
By a theorem that we won't prove, for any table $T_{1}$ and any $\bar{a}$\[
\Pr_{L_{1},L_{2}}\left[T_{1}\left(L_{1}\right)+T_{1}\left(L_{2}\right)\neq T_{1}\left(L_{1}+L_{2}\right)\right]\geq\frac{2}{9}\delta_{1}\]
So, if the table has at least fraction $\delta_{1}$ invalid entries,
this probability that we will reject is at least $\frac{2}{9}\delta_{1}$.
So, the chance of being fooled $F_{1}\leq1-\frac{2}{9}\delta_{1}$.
\end{proof}
\begin{lem}
The probability $F_{2a}$ that verification step $(2a)$ accepts has
$F_{2a}\leq1-\frac{2}{9}\delta_{3}$.
\end{lem}
\begin{proof}
As in the verification of (1), check the linearity condition $T_{2}\left(Q_{1}\right)+T_{2}\left(Q_{2}\right)=T_{2}\left(Q_{1}+Q_{2}\right)$.
If we each $Q\in Z_{2}$ as a matrix of coefficients $\left(c_{ij}\right)$,
and think of $T_{2}$ as a function of these coefficients, the linearity
property is satisfied for all $Q_{1}$ and $Q_{2}$ if and only if
the function $T_{2}\left(c_{11},\dots,c_{nn}\right)$ is a linear
function of the coefficients $\left(c_{ij}\right)$, i.e. there exists
coefficients $b_{ij}$ so that\[
Q\left(\bar{a}\right)=\sum_{i,j}c_{ij}b_{ij}\]


By the theorem we used without proof in the verification for (1),
if $T_{2}$ does not satisfy this linearity property for some fraction
of entries \[
\delta_{3}=\min_{\left(b_{ij}\right)}\left[\Pr_{\left(c_{ij}\right)\in\left\{ 0,1\right\} ^{n\times n}}\left[T_{2}\left(c_{11},\dots,c_{nn}\right)\neq\sum_{i,j}c_{ij}b_{ij}\right]\right]\]
, then the probability of us catching the error by the linearity check
\[
\Pr_{Q_{1},Q_{2}}\left[T_{2}\left(Q_{1}\right)+T_{2}\left(Q_{2}\right)\neq T_{2}\left(Q_{1}+Q_{2}\right)\right]\geq\frac{2}{9}\delta_{3}\]
So, the probability this step accepts is\[
F_{2a}\leq1-\frac{2}{9}\delta_{3}\]

\end{proof}
\begin{lem}
The probability $F_{2b}$ that verification step $(2b)$ accepts has
$F_{2b}\leq1-\delta_{2}\left(2\delta_{1}+\delta_{3}+\frac{3}{4}\right)$.
\end{lem}
\begin{proof}
We write out a polynomial $Q\in Z_{2}$ in terms of its coefficents
$(c_{ij})$ as \[
Q\left(\bar{a}\right)=\sum_{i,j}c_{ij}a_{i}a_{j}\]
Using the coefficient representation from the verification for (1b),
we associate $Q$ with its matrix of $n^{2}$ coefficients $C=\left(c_{ij}\right)$
so that\[
Q\left(\bar{a}\right)=\sum_{i,j}c_{ij}b_{ij}\]
So, to check that $Q$ is a quadratic polynomial, we need to check
that the row vector $\bar{a}=\left(a_{1},a_{2},\dots,a_{n}\right)$
has $b_{ij}=a_{i}a_{j}$ for each $i,j$, or equivalently that the
matrix $B=\bar{a}^{T}\bar{a}$. 

We do this using a well-known probabilistic test of matrix equality
by picking two random (row) vectors $x,y\in\left\{ 0,1\right\} ^{n}$
and checking that $xBy^{T}=x\bar{a}^{T}\bar{a}y^{T}$. If matrices
$B$ and $\bar{a}^{T}\bar{a}$ differ in some entry $i,j$, then with
probability at least $\frac{1}{4}$, $xBy^{T}\neq x\bar{a}^{T}\bar{a}y^{T}$,
since the equality depends on whether $x_{i}y_{j}=1$ or $0$, which
happen with probabilities $\nicefrac{1}{4}$ and $\nicefrac{3}{4}$.
The condition $xBy^{T}=\left(x\bar{a}^{T}\right)\left(\bar{a}y^{T}\right)$
is equivalent to \[
Q_{xy}\left(\bar{a}\right)=L_{x}\left(\bar{a}\right)L_{y}\left(\bar{a}\right)\]
where $L_{x}$ and $L_{y}$ are linear functions with coefficients
given by $x$ and $y$, and $Q_{xy}$ is the quadratic polynomial
with $c_{ij}=x_{i}y_{j}$. 

We check this by querying the tables, using the indirect query $T_{2}\left(L_{x}L_{y}+S\right)-T_{2}\left(S\right)$
with random $S$ for $T_{2}\left(L_{x}L_{y}\right)$. The check \[
T_{2}\left(S+L_{1}L_{2}\right)=T_{2}\left(S\right)+T_{1}\left(L_{1}\right)T_{1}\left(L_{2}\right)\]
will be false if $T_{2}$ reports an incorrect value for $S+L_{1}L_{2}$
or $S$, which happens with probability at least $\delta_{2}$, and
none of the following problems occur:
\begin{itemize}
\item $T_{1}\left(L_{1}\right)\neq L_{1}\left(\bar{a}\right)$ (probability
$\delta_{1}$)
\item $T_{1}\left(L_{2}\right)\neq L_{2}\left(\bar{a}\right)$ (probability
$\delta_{1}$)
\item $\sum_{i,j}c_{ij}b_{ij}=T_{2}\left(c_{11},\dots,c_{nn}\right)$ (probability
$\delta_{3}$)
\item $xBy^{T}=x\bar{a}^{T}\bar{a}y^{T}$ (probability $\nicefrac{3}{4}$
if $B\neq\bar{a}^{T}\bar{a}$)
\end{itemize}
So, the probability $F_{2b}$ of rejecting at this step satisfies\[
F_{2b}\leq1-\delta_{2}\left(2\delta_{1}+\delta_{3}+\frac{3}{4}\right)\]

\end{proof}
\begin{lem}
If $\phi$ has no satisfying assignment, the probability $F_{3}$
that verification step $(3)$ accepts has $F_{3}\leq\frac{1}{2}+\delta_{1}+2\delta_{2}$.
\end{lem}
\begin{proof}
If $\phi$ has no satisfying assignment, then for any $\bar{a}$,
$P_{i}\left(\bar{a}\right)=1$ for some $i$. With a constant number
of queries, we can't even check whether the tables claim that $P_{i}=0$
for each of the $m$ polynomials $P_{i}$, or even a substantial fraction.
However, we can use a trick from the Razborov-Smolensky proof of the
circuit lower bound of evaluating a random linear combination $A_{r}=\sum r_{j}p_{j}$,
which has $A_{r}\left(\bar{a}\right)=\sum r_{j}p_{j}\left(\bar{a}\right)$,
for random $r\in\left\{ 0,1\right\} ^{m}$. Since the coefficient
$r_{i}$ of a failing polynomial $P_{i}$ with $P_{i}\left(\bar{a}\right)=1$
is equally likely to be 0 or 1, so\[
\Pr_{r}\left[A_{r}\left(\bar{a}\right)=0\right]=\frac{1}{2}\]
The polynomial $A_{r}$ may not be homogenous. We can uniquely decompose
it as $A_{r}=Q_{r}+L_{r}+C_{r}$, with $Q_{r}\in Z_{2}$, $L_{r}\in Z_{1}$,
and $C_{r}$ constant. Then, checking if $A_{r}\left(a\right)=0$
equates to checking that $Q_{r}+L_{r}+C_{r}=0$.

We do this by checking whether $T_{2}\left(Q_{r}+S\right)-T_{2}\left(S\right)+T_{1}\left(L_{r}\right)+C_{r}=0$.
Since $A_{r}\left(\bar{a}\right)=Q_{r}\left(\bar{a}\right)+L_{r}\left(\bar{a}\right)+C_{r}\left(\bar{a}\right)$
and $\left(Q_{r}+S\right)\left(\bar{a}\right)-S\left(\bar{a}\right)=Q_{r}\left(\bar{a}\right)$,
if $\phi$ is not satisfiable, by union bound\begin{eqnarray*}
F_{1} & = & \Pr_{r}\left[T_{2}\left(Q_{r}+S\right)-T_{2}\left(S\right)+T_{1}\left(L_{r}\right)+C_{r}\neq0\right]\\
 & \leq & \Pr_{r}\left[A_{r}\left(\bar{a}\right)=0\right]+\Pr_{r}\left[T_{1}\left(L_{r}\right)\neq L_{r}\left(\bar{a}\right)\right]+\Pr_{r,S}\left[T_{2}\left(Q_{r}+S\right)\neq\left(Q_{r}+S\right)\left(\bar{a}\right)\right]+\Pr_{S}\left[T_{2}\left(S\right)\neq S\left(\bar{a}\right)\right]\\
 & = & \frac{1}{2}+\delta_{1}+2\delta_{2}.\end{eqnarray*}

\end{proof}


\begin{proof}
Note that $F\leq F_{1}F_{2a}F_{2b}F_{3}$ (this is an inequality,
since in $F$ we have the restriction of using the same $T_{1}$ and
$T_{2}$ for all the verification steps). So, from the Lemmas,\[
F\leq\left(\left[1-\frac{2}{9}\delta_{1}\right]\right)\left(\left[1-\frac{2}{9}\delta_{3}\right]\right)\left(\left[1-\delta_{2}\left(2\delta_{1}+\delta_{3}+\frac{3}{4}\right)\right]\right)\left(\left[\frac{1}{2}+\delta_{1}+2\delta_{2}\right]\right)\]
where, $\left[x\right]$ denotes $\min\left(x,1\right)$, since each
of the probabilities $F_{1},F_{2a},F_{2b},F_{3}$ are at most 1.
\end{proof}


A computer-aided calculation of the maximum value $F$ over $\delta_{1},\delta_{2},\delta_{3}\in\left[0,1\right]$
gives a maximum value of $\frac{8}{9}$. This proves the theorem.


\section{Next class}

Next class, we'll use a PCP scheme like the one shown to create a
reduction from $K$-coloring to $k$-coloring which has $\mbox{UNSAT}(\tilde{G})\geq\delta\mbox{UNSAT}(G)$
for constant $\delta$, thus satisfying Lemma \ref{lem:colorreduction}.
Proving this Lemma will complete the proof for the existence of a
polynomial-size PCP.
\end{document}
