\documentclass{article}
\usepackage{amssymb}
\begin{document}
\input{preamble.tex}
\lecture{20}{April 20, 2005}{Madhu Sudan}{Toby Schachman}
\section{Today}
\begin{itemize}
\item We introduce Approximability and Optimization and their relationship with PCP.
\item We begin Dinur's new proof (published two days ago!) of the PCP theorem. The proof is inspired
by previous papers by Dinur-Reingold. Recall the PCP theorem: ${\rm NP} \subseteq {\rm PCP}[O(log (n)),O(1)]$.
\end{itemize}
\section{Approximability and Optimization}
Consider the optimization problem of coloring a given graph with as few colors as possible. We know this problem is NP-hard (because 3-coloring a 3-colorable graph is NP-hard), but what about nearly-optimal colorings? For example, if we are given that a graph is $k$-colorable, is there a way to color the graph with $k+1$ colors in polynomial time? We know we can always color planar graphs with $k+1$ colors (because we have an algorithm for 4-coloring planar graphs) but it is open what we can do with generalized graphs. Approximability is the study of finding such near-optimal solutions.
Formally, a polynomial time algorithm $A$ approximates a problem to within $\alpha(\cdot)$ if for any instance $x$, $A(x)$ produces a solution whose ${\rm Cost} \leq \alpha(n) {\rm OPT}(x)$ where ${\rm OPT}(x)$ is the cost of the optimal solution and $\alpha(n) > 1$. Alternatively, if we are trying to maximize a quantity, we use ${\rm Profit} \geq {\rm OPT}(x)/\alpha(n)$.
For example, planar coloring has a $4/3$-approximating algorithm. For general coloring, the best known result for 3-colorable graphs is that we can color a 3-colorable graph with $n^{3/14}$ colors [Blum, Karger].
How would one prove that this is the best result, in other words that there is no polynomial time algorithm that can always color a 3-colorable graph with less than $n^(3/4)$ colors? What would a hardness reduction look like?
Well, we could give a transformation which maps 3cnf formula $\phi$ to graph $G_\phi$ such that
\begin{itemize}
\item $\phi \in {\rm SAT} \rightarrow G_\phi$ is 3-colorable
\item $\phi \not\in {\rm SAT} \rightarrow G_\phi$ is not k-colorable for $k 0$ there exists a transformation T' transforming 3cnf formulae to MAX $2{\rm -SAT-}\Sigma$ such that
$$
\phi \in {\rm SAT} \to {\rm UNSAT}(\phi)=0
$$
and
$$
\phi \not\in {\rm SAT} \to {\rm UNSAT}(T'(\phi)) \geq \epsilon
$$
Notice by the above claims this is equivalent to the PCP theorem. We prove the theorem with a main lemma which is then proved by two sub-lemmas.
\section{Main Lemma}
For some constant $\Sigma$, $\epsilon > 0$, there exists a transform T transforming MAX $2{\rm -SAT-}\Sigma$ instances to MAX $2{\rm -SAT-}\Sigma$ preserving satisfiability such that
$$
{\rm UNSAT}(T(\phi)) \geq \min\{\epsilon,2 {\rm UNSAT}(\phi)\}
$$
and further $|T(\phi)|$ is $O(|\phi|)$.
The theorem follows from this lemma. Start by transforming $\phi$ to $T_0(\phi)$, and instance of MAX $2{\rm -SAT-}\Sigma$ such that $T_0(\phi)$ is satisfiable if and only if $\phi$ is satisfiable. Now apply T to $T_0(\phi)$ a logarithmic number of times so that UNSAT is sufficiently low and $|T'(\phi)|$ is $O(n \log(n))$.
We prove this main lemma from two sub-lemmas.
\section{Lemma 1: Amplification}
For every $\beta$ and $\Sigma$ there exists a $l$ and a transform $T_1$ from MAX $2{\rm -SAT-}\Sigma$ to MAX $2{\rm -SAT-}\Sigma^l$ preserving satisfiability such that
$$
{\rm UNSAT}(T_1(\phi)) \geq \beta \cdot {\rm UNSAT}(\phi)
$$
and further $|T_1(\phi)| = O(|\phi|)$.
Notice that this lemma improves soundness but at the expense of a larger alphabet. We will defer the proof of this lemma until we cover derandomization techniques.
\section{Lemma 2: Alphabet Reduction}
There exists alphabet $\Sigma$ and constant $c$ such that for every finite alphabet $\Gamma$ there is a transform $T_2$ from MAX $2{\rm -SAT-}\Gamma$ to MAX $2{\rm -SAT-}\Sigma$ preserving satisfiability and such that
$$
{\rm UNSAT}(T_2(\phi)) \geq 1/c \cdot {\rm UNSAT}(\phi)
$$
Furthermore $|T_2(\phi)| = O(|\phi|)$. Notice that this lemma decreases soundness but also decreases the alphabet size. We can combine it with lemma 1 to prove the main lemma.
\section{Main Lemma from Sub-Lemmas}
\begin{itemize}
\item Set $\Sigma$ as in Lemma 2.
\item Set $\beta = 2c$
\item Set $\Gamma$ to $\Sigma^l$ from Lemma 1.
\item Consider the transform $T = T_2 \circ T_1$. $T$ is linear sized, polynomial time, and preserves satisfiability. Furthermore,
\begin{eqnarray*}
{\rm UNSAT}(T(\phi)) & = & {\rm UNSAT}(T_2(T_1(\phi))) \\
& \geq & 1/c \cdot {\rm UNSAT}(T_1(\phi)) \\
& \geq & \beta/c \cdot {\rm UNSAT}(\phi) \\
& = & 2 \cdot {\rm UNSAT}(\phi)
\end{eqnarray*}
\end{itemize}
\section{Proof Outline for Lemma 2}
We ended with a proof outline of lemma 2, which we will prove next class. We break lemma 2 down into two more lemmas:
\begin{itemize}
\item Lemma 2a: There exists constants $k$ and $c_a$ such that for every finite $\Gamma$, there is a transform $T_{2a}$ from MAX $2{\rm -SAT-}\Gamma$ to MAX $k{\rm -SAT-}\{0,1\}$ preserving satisfiability such that
$$
{\rm UNSAT}(T_{2a}(\phi)) \geq 1/{c_a} \cdot {\rm UNSAT}(\phi)
$$
and further, $T_{2a}$ is linear.
\item Lemma 2b: For every $k$ there is a transform $T_{2b}$ MAX $k{\rm -SAT-}\{0,1\}$ to MAX $2{\rm -SAT-}\{0,1\}^k$ such that
$$
{\rm UNSAT}(T_{2b}(\phi)) \geq 1/k \cdot {\rm UNSAT}(\phi)
$$
and further, $T_{2b}$ is linear and preserves satisfiability. The proof of this lemma is analogous to reducing oracle interactive proofs to 2-prover interactive proofs.
\end{itemize}
\end{document}