\documentclass[a4paper,10pt,twocolumn,oneside]{article}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Packages %%

\usepackage{latexsym}     % More symbols 
\usepackage{amsmath}      % Generic math commands etc.
\usepackage{amsfonts}     % Fonts for math
\usepackage{amssymb}      % Symbols for math
\usepackage{theorem}      % Custom theorem-style environments
\usepackage{rotating}     % Rotating material

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Environments for math %%

{\theorembodyfont{\rmfamily}
\newtheorem{Def}{Definition}[section]}
{\theorembodyfont{\rmfamily}
\newtheorem{ExaTh}[Def]{Example}}
{\theorembodyfont{\rmfamily}
\newtheorem{Prob}[Def]{Problem}}
\newtheorem{Thm}[Def]{Theorem}
\newtheorem{Lem}[Def]{Lemma}
\newtheorem{Cor}[Def]{Corollary}
\newenvironment{Proof}{\textit{Proof.}}{\hfill $\blacksquare$}
\newenvironment{Sketch}{\textit{Proof sketch.}}{\hfill $\blacksquare$}
\newenvironment{Exa}{\begin{ExaTh}}{\hfill $\diamondsuit$\end{ExaTh}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Math-mode abbreviations %%

\newcommand{\Z}{\ensuremath{\mathbb{Z}}}
\newcommand{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\F}{\ensuremath{\mathbb{F}}}
\newcommand{\Nat}{\ensuremath{\mathbb{N}}}
\newcommand{\Prb}{\operatorname{Pr}}
\newcommand{\Poly}{\ensuremath{\mathbf{P}}}
\newcommand{\BPP}{\ensuremath{\mathbf{BPP}}}
\newcommand{\Polytime}{\ensuremath{\mathbf{P}}}
\newcommand{\NP}{\ensuremath{\mathbf{NP}}}
\newcommand{\PCP}{\ensuremath{\mathbf{PCP}}}
\newcommand{\IP}{\ensuremath{\mathbf{IP}}}
\newcommand{\AM}{\ensuremath{\mathbf{AM}}}
\newcommand{\AMpoly}{\ensuremath{\mathbf{AM}\mathrm{(poly)}}}
\newcommand{\PSPACE}{\ensuremath{\mathbf{PSPACE}}}
\newcommand{\yes}{\ensuremath{\mathrm{yes}}}
\newcommand{\no}{\ensuremath{\mathrm{no}}}
\newcommand{\accept}{\ensuremath{\mathrm{accept}}}
\newcommand{\reject}{\ensuremath{\mathrm{reject}}}
\newcommand{\bra}{\ensuremath{\langle}}
\newcommand{\ket}{\ensuremath{\rangle}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Document starts %%

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Title %%

\newcommand{\DRAFT}{
\newlength{\draftfboxsepsave}
\setlength{\draftfboxsepsave}{\fboxsep}
\newlength{\draftfboxrulesave}
\setlength{\draftfboxrulesave}{\fboxrule}
\begin{flushright}
\raisebox{3cm}[0pt][0pt]{
\begin{turn}{-20}
\setlength{\fboxsep}{1mm}
\setlength{\fboxrule}{2mm}
\fbox{%
\begin{tabular}{c}
\bf \large DRAFT\\
\bf \large \today
\end{tabular}%
}
\end{turn}
}
\end{flushright}
\setlength{\fboxsep}{\draftfboxsepsave}
\setlength{\fboxrule}{\draftfboxrulesave}
}

\title{%\DRAFT 
T-79.511 Special Course on Cryptology / Zero Knowledge:\\ 
Comments on ``A first look at the $\NP=\PCP(\log n, 1)$ theorem''}
\author{Petteri Kaski}
%\date{}
\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Article body %%

\section{Introduction}
The purpose of this document is to give comments and constructive criticism on 
the manuscript \cite{K01} describing the ``PCP Theorem'' \cite{A94,AS98b}, 
which characterizes $\NP$ as the class of languages $L\subseteq \{0,1\}^*$ 
whose instances $x\in L$ admit polynomial-length membership proofs 
$y\in \{0,1\}^*$ verifiable by a probabilistic polynomial time Turing machine 
using $O(\log |x|)$ random bits and $O(1)$ bits from the proof string $y$.

First some general comments. The manuscript succeeds well in conveying
the key ideas and constructions that underlie the PCP Theorem. The 
constructions are given in sufficient detail to provide the reader familiar
with basic notions of algebra and computational complexity a strong
intuition of the theorem. Furthermore, omission of detailed analysis 
is justified since it would be impossible to present in a short survey.
All in all, the manuscript is well-written, although (easily correctable)
minor inconsistencies can be found.

The main reference used is a revised version of Sanjeev Arora's 
thesis \cite{A94}, which gives a self-contained treatment of the PCP Theorem.
The article \cite{AS98b} (see also \cite{AS98}), although arguably 
less self-contained, contains a more recent proof of the PCP Theorem,
including more accurate definitions in particular for verifier composition 
and encoding/decoding schemes. (It would be nice to mention this article in 
the references of the manuscript.)



\section{Comments and suggestions on specific topics}
\textbf{Optimality of the characterization}.
The characterization $\NP=\PCP(\log n, 1)$ is optimal in the sense that
if $\NP\subseteq \PCP(o(\log n),o(\log n))$, then $\Polytime=\NP$ \cite{AS98}. 
This would be nice to mention in the manuscript.

Furthermore, the PCP Theorem can be stated in a form where the number
of queries is a fixed constant for all languages in $\NP$ (assuming 
a soundness error of at most 1/2) \cite[Theorem 1.2.1]{AS98b}.
Definitions 1.1 and 1.3 in the manuscript imply only that a 
language-dependent constant exists.

\textbf{Gap/promise problems}.
The definition of \textsc{MAX-3SAT($\epsilon$)} could be written more clearly.
For example: ``Call a \textsc{3SAT}-instance \emph{less than 
$\delta$-satisfiable} if every truth assignment satisfies less than 
a $\delta$-fraction of its clauses. The problem
\textsc{MAX-3SAT($\epsilon$)} is to decide the satisfiablity of 
a 3SAT instance $\phi$ that is guaranteed to be either (a) satisfiable or 
(b) less than $(1-\epsilon)$-satisfiable.'' 
(In particular, if neither (a) nor (b) holds, then the behaviour of the 
decision algorithm may be arbitrary.)

\textbf{Definition 1.2}. Exactly one of the 
occurences of $c$ should be replaced by $1-c$ for the sentence in part (ii) 
to be consistent with the notation. Also, given that random access is
allowed to the proof, the proof string length should probably be explicitly 
upper bounded by a polynomial in the input length.

\textbf{Theorem 1.5}.
\emph{The ``only if'' direction}. An acceptance probability of 
less than $1-\epsilon$ in the nonmembership case is sufficient by 
Definitions 1.2--1.3 to guarantee $L\in \PCP(\log n,1)$, 
so why is it necessary to reduce it to 1/2?
Also, strictly speaking, the ``only if'' part of the proof only proves
$\NP\subseteq \PCP(\log n,1)$. (The reverse inclusion naturally holds
without the $\NP$-hardness assumption, as stated later in Theorem 1.6 of 
the manuscript.)

\emph{The ``if'' direction}. 
The subscript ``$c$'' is unspecified. With Definitions 1.2 and 1.3 it cannot
be assumed that at least half of the $\phi_{\psi,r}$ contain a clause
that is not satisfied. 

\textbf{Definition 2.1}.
It would assist the reader if the definition would explicitly
state that the size of the ``symbol'' alphabet is in general a function
of the input size, and that the ``symbols'' can w.l.o.g. be assumed to
be encoded by bit strings whose length depends on the symbol alphabet size.

\textbf{Definition 2.2}.
The constant $c$ is undefined. The role of integer $p$ is unclear, namely,
is it a parameter to the subroutine or a fixed constant. 
The expression ``if all the $z_i$'s are codewords'' should be replaced 
by ``if all the $z_i$'s are $\delta/3$-close'' for consistency.

\textbf{Coding-theoretic definitions}.
Does the constant $n$ denote the input size in ``$C\subset A^n$''? 
The ``goodness'' of a code is defined somewhat inaccurately.%
\footnote{It is impossible 
that there exist two distinct codewords that have (relative) distance 
less than $\delta/2$ to any fixed noncodeword.
(If this were possible, then an application of the
triangle inequality would produce a contradiction to $\delta$ being 
the (relative) minimum distance of the code.)
So, unique decoding is \emph{always} guaranteed if the noncodeword
is $\delta/2$-close (to a codeword).}

\textbf{Lemma 2.4}. The reviewer would like to suggest
\cite{AS98,AS98b} as an alternative references for the proof of the 
Composition Theorem. 

The proof sketch could indicate explicitly that the $(Q+1)$-part 
encoded proof verification capability of $V_2$ is used. 
Also, the $y_{Q+1}(\gamma)=\pi_\gamma$ selection could be justified
in more detail; cf.\ \cite[p.\ 22]{A94} or \cite{AS98b}. 

\textbf{Identification of $\{0,\ldots,N\}$ with a subset of $\F_q^m$}. 
The word ``isomorphism'' should probably be replaced by ``bijection'' in
the context $\xi:\{0,\ldots,N\}\rightarrow\{0,\ldots,h\}^m$? 

\textbf{Low degree test and interpolation}. 
The term ``hard case'' is ambiguous. 
The interpolation algorithm is somewhat inaccurate; 
if $\kappa:\F_q\rightarrow \F_q^m$, then evidently $z_{s+1}\in_U \F_q^m$.
Moreover, it is not immediately clear (at least to the reviewer) that 
Procedure 4.2-(ii) in \cite[p.\ 56]{A94} (upon which the reviewer assumes
the interpolation algorithm to be based) would correspond to the 
interpolation algorithm presented in the manuscript. 
In particular, Procedure 4.2-(ii) makes a random
selection from the $q^m$ curves in $P(\bra z_1,\ldots,z_s\ket)$, the set
of degree $s$ curves in $\F_q^m$ whose first%
\footnote{With respect to a ``canonical'' linear order on $\F_q$.}
$s$ points are $z_1,\ldots,z_s$. Thus, it is the reviewer's understanding
that the values $y_1,\ldots,y_s$ selected uniformly at random from $\F_q$ 
in the manuscript are in fixed in Procedure 4.2-(ii). 
Whether this affects the correctness of the algorithm remains open.

\textbf{Arithmetization of a 3SAT-instance}.
The definition of $\chi_j$ should read ``$\chi_j(c,v)=1$ if $v$ is the $j$th 
variable of the clause $c$ from $\phi$ and $\chi_j(c,v)=0$ otherwise.''
Also, it would clarify the presentation if it were explicitly indicated
that 
\[
\prod_{j=1}^3\chi_j(c,v_j)(s_j(c)-f(v_j))=0
\]
is an equation system with one equation for each choice
$c,v_1,v_2,v_3\in \{0,\ldots,h\}^m$. Furthermore, $g_f\equiv 0$ holds
if and only if $f$ encodes a satisfying truth assignment for $\phi$. 


\section{Suggestions for discussion}

\textbf{Number of proof queries required to recognize $\NP$}. 
What is the minimum number of proof queries sufficient to recognize
all languages in $\NP$?
Is e.g. one bit of the proof sufficient to guarantee a soundness error of 
at most 1/2?

\textbf{Nonuniformity}. 
How is the class $\PCP(r,q)$ affected if we allow the verifier to be 
a nonuniform (probabilistic polynomial-time) Turing machine?

\textbf{Applicability of the techniques}.
Are the techniques applied in the proof of the PCP theorem also applicable
in other contexts? For example, what other well-known complexity classes 
besides $\NP$ can be characterized using the PCP formalism by varying
the random string and the number of queries allowed?
(See e.g. \cite{AS98b} and the references therein for a partial answer;
are there more recent results?)




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% References %%


\begin{thebibliography}{XX}
\bibitem{A94}
S.\ Arora.
\emph{Probabilistic Checking of Proofs and Hardness of Approximation Problems}.
Technical Report CS-TR-476-94, Department of Computer Science, Princeton 
University, 1994.
(Revised version of a dissertation submitted at CS Division, UC Berkeley, 
August 1994.)

\bibitem{AS98}
S.\ Arora and S. Safra.
Probabilistic Checking of Proofs: A New Characterization of NP.
\emph{J.\ ACM} \textbf{45} (1998) no. 1, 70--122.

\bibitem{AS98b}
S.\ Arora, C.\ Lund, R.\ Motwani, M.\ Sudan and M.\ Szegedy.
Proof Verification and the Hardness of Approximation Problems.
\emph{J.\ ACM} \textbf{45} (1998) no. 3, 501--555.

\bibitem{K01}
M.\ Kojo.
T-79.511 Special Course on Cryptology / Zero Knowledge: 
A first look at the $\mathrm{NP}=\mathrm{PCP(\log n,1)}$ theorem.
October 19, 2001.

\end{thebibliography}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Appendix %%

\end{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Document ends %%

