%% ToC156.tex -->  a007.tex   Haastad - Khot    9-28-2005

\documentclass{toc}

\tocdetails{%
  volume=1, number=7, year=2005, firstpage=119,
  received={October 21, 2004},
  revised={August 23, 2005},
  published={September 28, 2005}}

\DeclareMathOperator{\mult}{mult}
\DeclareMathOperator{\Acc}{Acc}
\DeclareMathOperator{\AND}{AND}

\runningtitle{Query Efficient PCPs with Perfect Completeness}
\runningauthor{J.~{H\aa stad} and S.~Khot}
\copyrightauthor{Johan~{H\aa stad} and Subhash~Khot}

\bibliographystyle{tocplain}

\begin{document}

\begin{frontmatter}
\title{Query Efficient PCPs with Perfect Completeness}

\author[johan]{Johan H\aa stad\thanks{%
Work done while visiting the Institute for
Advanced Study, supported by NSF grant CCR-9987077.}}

\author[subhash]{Subhash Khot\thanks{%
Work done while the author was at Princeton University.}}

\tocpdftitle{Query Efficient PCPs with Perfect Completeness}
\tocpdfauthor{J. Hastad and S. Khot}

\tockeywords{Computational complexity, approximation algorithms,
  probabilistically checkable proofs, PCP, inapproximability, amortized
  query bits, perfect completeness, amortized query bits}
\tocams{68Q25}
\tocacm{F 2.2}

\begin{abstract}
  For every integer $k > 0$, and an arbitrarily small constant
  $\epsilon>0$, we present a PCP characterization of NP where the
  verifier uses logarithmic randomness, non-adaptively queries
  $4k+k^2$ bits in the proof, accepts a correct proof with probability
  1, i.\,e., it has perfect completeness, and accepts any supposed proof
  of a false statement with probability at most $2^{-k^2}+\epsilon$.
  In particular, the verifier achieves optimal {\it amortized query
    complexity} of $1+\delta$ for arbitrarily small constant $\delta >
  0$. Such a characterization was already proved by Samorodnitsky and
  Trevisan (STOC 2000), but their verifier loses perfect completeness
  and their proof makes an essential use of this feature.

  By using an adaptive verifier, we can decrease the number of query
  bits to $2k+k^2$, equal to the number obtained by Samorodnitsky and
  Trevisan.  Finally we extend some of the results to PCPs over
  non-Boolean alphabets.
\end{abstract}
\end{frontmatter}

\section{Introduction}

The celebrated PCP Theorem (\cite{arsa}, \cite{almss}) gives a way of writing 
proofs for (purported) NP statements such that the proofs can be checked very 
efficiently by a probabilistic verifier. The verifier needs a very limited 
amount of random bits and reads only a constant number of bits from the proof. 
Moreover, a correct statement always has a proof that is accepted with probability 
$1$ (or close to $1$) and \emph{any} proof of an incorrect statement is accepted 
only with a tiny probability (called error probability or soundness). 

PCPs have surprising connections, first discovered by
Feige et al. \cite{fglss},
to inapproximability results, i.\,e., results 
showing that computing even approximate solutions to some NP-complete problems 
is hard.  
The discovery  of the PCP Theorem  opened up a whole 
new fascinating direction for proving various  inapproximability  
results.  In the last decade or so, quantitative improvement in 
the efficiency of PCP verifiers has led to (in many cases optimal)
inapproximability results for many 
optimization problems (\cite{bgs}, \cite{f}, \cite{h},
 \cite{hastad}, \cite{st}, \cite{ghs}).   
For  different applications, different aspects of the
given PCP need to be optimized.  For a detailed discussion
of various parameters we refer to \cite{bgs}.

In the current paper we are mostly concerned with making efficient
use of queries, i.\,e., to obtain very strong PCPs where the
verifier reads very few symbols in the proof. More specifically, we are 
interested in the trade-off between the number of queries and the error 
probability. 

Samorodnitsky and Trevisan \cite{st} obtained very strong results
along these lines, giving a PCP where the verifier reads
$2k+k^2$ bits, almost always accepts a correct proof of
a correct statement and accepts a proof of an incorrect
statement with probability only marginally larger than
$2^{-k^2}$.  This is a very impressive result in that
each read bit essentially decreases the probability of being
fooled by a factor of 2. Their verifier achieves {\it amortized query 
complexity} of $1+\delta$ for any $\delta > 0$ which is optimal 
(see \cite{bgs}). The amortized query complexity, when
we (almost) always accept a correct proof, is formally defined as 
the ratio between the number of queries ($2k+k^2$ in this case) 
and the logarithm of inverse 
of the error probability ($k^2$ in this case). 

The fact that the verifier sometimes rejects a correct proof of a
correct statement is called imperfect completeness and in
their construction Samorodnitsky and Trevisan make  essential use
of this property of the verifier.  For many reasons it is
preferable to have perfect completeness.
Firstly, it is natural to have a proof system where a correct proof
of a correct statement is always accepted.  Secondly, perfect
completeness is sometimes essential to obtain further results.
Some inapproximability results such as graph coloring sometimes
make essential use of perfect completeness and when using a given protocol
as a subprotocol in future protocols, perfect completeness, to
say the least, simplifies matters.

Several results in the past have focused on achieving 
PCPs with perfect completeness and this task many times turns out to be 
harder than obtaining corresponding PCPs without this
property. For instance, H\aa stad shows that 3SAT and $4$-Set Splitting are  
hard to approximate within ratio $\frac{8}{7}+\epsilon$.  
These results follow from the basic $3$-bit PCP
of \cite{hastad} establishing hardness for approximating
the number of satisfied linear equations mod 2.
To extend these results to satisfiable instances, however, requires   
a new PCP construction and a technically more complicated proof.

The main result of the current paper
is to extend the result of Samorodnitsky and Trevisan to include
perfect completeness.

\begin{theorem} \label{thm:main}  For any integer
$k>0$ and any $\epsilon >0$, any language in NP  has a PCP verifier that 
queries  $4k+k^2$ bits, has perfect completeness
and accepts a proof of an incorrect statement 
with probability at most $2^{-k^2}+\epsilon$. 
\end{theorem} 

Our result is based on a basic non-linear test which reads $5$ bits 
$(b_1,b_2,b_3,b_4,b_5)$ from the proof and accepts if 
$b_1 = b_2 \oplus  b_3 \oplus (b_4 \land b_5)$. We call this 
constraint  Tri-Sum-And and let MAX-TSA be the problem of 
satisfying the maximum number of such  constraints. We have the  
following theorem.
\begin{theorem} \label{thm:max tsa}
For any $\epsilon>0$, it is NP-hard to distinguish satisfiable
instances of Max-TSA from those where it is only possible
to simultaneously satisfy
a fraction $\frac {1}{2} + \epsilon$ of the constraints.
\end{theorem}
The choice to study Tri-Sum-And is somewhat arbitrary but
guided by our goal to achieve perfect completeness
while keeping the analysis simple.  To get perfect completeness
we need a nonlinear predicate while the analysis is
greatly aided by having as much linearity as possible present
in the predicate.  These two conflicting requirements led
to the choice of Tri-Sum-And.

Note that \thmref{thm:max tsa} is tight for Max-TSA
in that a random assignment satisfies
half the constraints.  There are stronger results for other
constraints on 5 bits and in particular Guruswami et al.
\cite{glst} give  a different
predicate for which $\frac{1}{2}$ can be improved to $\frac{7}{16}$.

We then iterate the basic test underlying \thmref{thm:main} in a way
similar to that used by Samorodnitsky and Trevisan, where they iterate
the basic $3$-bit test by H\aa stad.
We present two iterated tests: The first, which we call the
``complete
bipartite graph PCP,'' is analyzed in a way analogous to
the Samorodnitsky-Trevisan analysis and the second, which we call the ``almost
disjoint sets PCP,'' is analyzed in a way analogous to how H\aa stad and
Wigderson \cite{hw} analyzed the test of Samorodnitsky and Trevisan.

By a standard reduction the PCP results imply the following
theorem.

\begin{theorem} \label{thm:hard CSP} The Boolean constraint    
satisfaction problem on $k$  variables is hard to approximate 
within ratio $2^{k - O(\sqrt{k})}$ on satisfiable instances. 
\end{theorem} 

This should be contrasted with the approximation algorithm
by Trevisan~\cite{t} that shows that it is possible
to approximate the Boolean constraint                         
satisfaction problem on $k$  variables within $O(2^k/k)$
on satisfiable instances.

A test is called non-adaptive if which bits to read are decided before
the first bit is read and hence this set is independent
of the actual proof.  All the above mentioned PCPs are non-adaptive
which is in fact necessary to obtain \thmref{thm:hard CSP}.

If we allow adaptive tests then by making an iterated version
of a test in \cite{glst} we can get essentially the same parameters
as Samorodnitsky and Trevisan and thus simply gain perfect completeness.

\begin{theorem} \label{thm:adaptive}
For any integer $k>0$ and any $\epsilon>0$,
any language in NP has an adaptive PCP verifier that 
queries  $2k+k^2$ bits, has perfect completeness
and accepts a proof of an incorrect statement 
with probability at most $2^{-k^2}+\epsilon$. 
\end{theorem} 

\noindent
If we convert the test to be non-adaptive,
this test would read $2k+2k^2$ different bits and hence this
result does not strictly dominate \thmref{thm:main}.

\noindent
We extend some of our results to non-Boolean domains and in
particular we have the following theorem.
\begin{theorem} \label{thm:modp}
For every prime $p$,  the constraint 
satisfaction problem on $k$  variables over an alphabet of 
size $p$ is hard to approximate 
within ratio $p^{k - O(\sqrt{k})}$ on satisfiable instances. 
\end{theorem} 

We hope that our results will  be useful in the future to prove strong 
hardness results for approximate graph coloring. One such result 
by Khot \cite{kh} is  
\begin{theorem}[\cite{kh}]
There is an absolute constant $c>0$ such that it is 
 NP-hard to color a $k$-colorable graph with $k^{c\log k}$ 
colors. 
\end{theorem} 
Actually this result can be proved from the original form of the
Samorodnitsky-Trevisan result and perfect completeness is not
strictly required. But using our PCP with perfect completeness, this
result becomes more straightforward. On a related note one can observe
that perfect completeness is essential in the hypergraph coloring
results by Guruswami, H\aa stad and Sudan \cite{ghs}, and in general it
is a subtle problem to determine 
which coloring inapproximability results require
perfect completeness in the underlying PCP.

\subsection{Overview of the paper} 
This is the complete version of the extended abstract \cite{hk}. The
paper is organized as follows.  \secref{sec:prelim} introduces
techniques used in this paper. In \secref{sec:Boolean} we give our
results for the Boolean case: \secref{sec:basic} gives our basic
$5$-bit test, and \secref{sec:iterated binary} describes our iterated
tests.  \secref{sec:mod p} extends some of the results of
\secref{sec:Boolean} to non-Boolean domains.  \secref{sec:conclusion}
concludes with a few remarks.


\section{The general setup}\label{sec:prelim}

In this section we provide the necessary background.

\subsection{Notation}
Throughout the paper, 
we have Boolean functions in $\pm 1$ notation with $-1$ as 
logical true.
We use multiplication to denote exclusive-or, $\land$ for
the logical AND function.  As we use $-1$ to denote true
we have
$$
x \land y = \AND(x,y)= \frac {1+x+y-xy}{2}\enspace.
$$
Our default is that AND is highest level connective
and in particular
$$
xy \land zw = (xy) \land (zw)\enspace.
$$
Addition is used only over the real and complex numbers.

\subsection{The 2-prover protocol}

Many efficient PCPs, such as the one given in \cite{st}, are
conveniently analyzed using the formalism of an outer and inner
verifier.  This could also be done here, but to avoid too much
formalism we give a more explicit analysis.  Using the results of
\cite{almss} (as explicitly done in \cite{f}) one can prove that there
is a constant $c<1$ such that it is NP-hard to distinguish satisfiable
3-SAT formulas from those where only a fraction $c$ of the clauses can
be simultaneously satisfied by any assignment.  This formula can
furthermore have the property that any clause is of length exactly 3
and any variable appears in exactly 5 clauses.

Given a 3-SAT formula $\varphi = C_1 \land C_2 \ldots \land C_m$
which is either satisfiable or where one can only satisfy
a fraction $c$ of the clauses,  one can design a two-prover interactive
proof system with verifier $V$ as follows.

\medskip
\noindent
\textbf{Basic two-prover protocol}

\begin{enumerate}
\item $V$ chooses a clause $C_k$ uniformly at random and
a variable $x_j$, again uniformly at random, appearing
in $C_k$.  $V$ sends $k$ to prover $P_1$ and $j$ to prover $P_2$.

\item $V$ receives a value for $x_j$ from $P_2$ and values
for all variables appearing in $C_k$ from $P_1$.  $V$ accepts
if the two values for $x_j$ agree and the clause $C_k$ is
satisfied.
\end{enumerate}

It is not difficult to see that if a fraction $c$ of the clauses
can be satisfied simultaneously then the optimal strategy
of $P_1$ and $P_2$ convinces $V$ with probability $(2+c)/3$.
Thus it is NP-hard to distinguish the case when this probability
is 1 and when it is some constant strictly smaller than 1.
Note also that if we start with a formula where each variable
appears the same number of times, $V$ could first choose a 
random variable and then a random clause containing that
variable and get the same distribution.

To make the gap larger,  one runs this protocol $u$ times in
parallel resulting in the following protocol.

\medskip
\noindent
$\textbf{{\em u}-parallel two-prover protocol, 2PP({\em u})}$  

\begin{enumerate}
\item $V$ chooses $u$ clauses $(C_{k_i})_{i=1}^u$ uniformly at random and
for each $i$, $V$ chooses a variable $x_{j_i}$,
again uniformly at random, appearing in $C_{k_i}$.
$V$ sends $({k_i})_{i=1}^u$ to prover $P_1$ and 
$({j_i})_{i=1}^u$ to prover $P_2$.

\item $V$ receives values for $(x_{j_i})_{i=1}^u$ from $P_2$ and values
for all variables appearing in $(C_{k_i})_{i=1}^u$ from $P_1$.  $V$ accepts
if the two values for $x_{j_i}$ agree for each $i$ and all the picked
clauses are satisfied.
\end{enumerate}

We let $U$ denote the set of variables
sent to $P_2$, i.\,e., $(x_{j_i})_{i=1}^u$ while the set of
variables that $P_1$ gives values to is denoted by $W$.  Note
that $U \subset W$.

By the fundamental result by Raz \cite{r}, the probability
that the verifier accepts in 2PP$(u)$
when only a constant fraction $c<1$ of
the clauses can be simultaneously satisfied is bounded by $d_c^u$ for some
absolute constant $d_c <1$.  Let us formulate these properties
for future reference.

\begin{theorem}\label{thm:2ppu}
Let 2PP$(u)$ be the $u$ parallel version of the basic
two-prover protocol.  Then if only a fraction $c<1$ of
the clauses of $\varphi$ can be simultaneously satisfied,
then no strategy of $P_1$ and $P_2$ can make the verifier
accept with probability greater than $d_c^u$.  Here $d_c < 1$
is a constant that only depends on $c$.
\end{theorem}

\subsection{Long codes}

To turn  the protocol 2PP$(u)$ into a written proof that
can be checked very efficiently,  it is natural to, for
each question to either $P_1$ or $P_2$, write down
the answer in coded form.  As many other papers we
use the \emph{long code} introduced by Bellare et al. \cite{bgs}.

\begin{definition}
The \emph{long code} of an assignment $x \in \{ -1 ,1\}^t$ is
obtained by writing down 
for each function $f: \{ -1, 1\} ^t \to \{ -1,1\}$, 
the value $f(x)$.
\end{definition}

Thus the long code of a string of length $t$ is a string of
length $2^{2^t}$.  Note that even though a prover is supposed
to write down a long code for an assignment
a cheating prover might write down a
string which is not the correct long code of anything.
We analyze such arbitrary tables by 
Fourier expansion. 

\subsubsection{Fourier analysis} 
In this section, 
we explain the basics of the Fourier method. Let 
$${\cal F} = \bigl\{ f \ |  \ \{-1,1\}^t \to \{-1,1\} \bigr\} $$ 
and consider the vector space of all ``tables'' $A : {\cal F} \to {\R}$.
Here the addition of two tables is defined as pointwise addition and
the dimension of this vector space is $|{\cal F}| = 2^{2^t}$.  One can
define a natural inner product on this space by letting the inner
product of two tables $A_1$ and $A_2$ be
$$
\langle A_1, A_2\rangle \ = \ 2^{-2^t}  \sum_f  A_1(f) A_2(f)\enspace.
$$ 
For $\alpha \subseteq \{-1,1\}^t$, let $\chi_\alpha$ be a Boolean-valued 
(i.\,e., $\{-1,1\}$-valued) table defined as 
$$
\chi_\alpha (f) =  \prod_{x \in \alpha} f(x)  \quad \ \forall \ f \ \in {\cal F}\enspace.
$$ 
The $\chi_\alpha$ are called \emph{characters}.
The characters are multiplicative, i.\,e.,
$$
\chi_\alpha (f_1f_2)= \chi_\alpha(f_1) \chi_\alpha (f_2)\enspace.
$$
The characters are in fact symmetric in $\alpha$ and $f$ but
as we have used set notation for $\alpha$ we have
\begin{eqnarray}\label{eq alpha prod}
\chi_{\alpha_1} (f) \chi_{\alpha_2} (f)
=\chi_{\alpha_1 \oplus \alpha_2} (f)
\end{eqnarray}
where $\alpha_1 \oplus \alpha_2$ is the exclusive-or of the characteristic
vectors of the sets $\alpha_1$ and $\alpha_2$.  Put differently,
$\alpha_1 \oplus \alpha_2$ is the
set which is the symmetric difference of $\alpha_1$ and
$\alpha_2$.

The set of
characters (there are $2^{2^t}$ of them) forms an orthonormal basis for the 
vector space. Thus any table $A$ can be expressed as 
$$
A(f) \ = \  \sum_{\alpha \subseteq \{ -1,1\}^t} \hat A_\alpha \chi_\alpha (f)\enspace,
$$
where $\hat A_\alpha$ are real numbers called \emph{Fourier coefficients}; they can 
found as
$$
\hat A_\alpha \ =  \  \langle A, \chi_\alpha \rangle = \  2^{-2^t} \sum_{f} \hat A(f) \chi_\alpha (f)\enspace.
$$
If $A$ is Boolean valued, we have Parseval's identity $\sum_\alpha \hat 
A_\alpha^2 = 1$. 
If $A$ is indeed a correct long code of a string $x^{(0)}$ then
$\hat A_{\{ x^{(0)}\}} =1$ while all the other Fourier coefficients
are 0.

In our protocols we pick
a function uniformly and then
often perform an analysis using the Fourier expansion.
The following lemma is simple but powerful.

\begin{lemma}\label{lem:exp chi}
Assume that $f$ is picked with the uniform distribution
then for  $\alpha\not= \emptyset$,
$$
E_f [\chi_\alpha(f)] =0
$$
while
$$
E_f [\chi_\emptyset(f)] =1\enspace.
$$
\end{lemma}

Using this lemma together with \eqref{eq alpha prod} enables
us to compute the expected value of products of
characters in a simple way.

We can, to a limited extent, put some restrictions on the
tables produced by the prover.

\begin{definition}
A table $A$ is folded over true if $A(f)=-A(-f)$ for
any $f$.
\end{definition}

\begin{definition}
A table $A$ is conditioned upon a function 
$h : \{-1,1\}^t \to \{-1,1\}$,  if $A(f)=A(f\land h)$
for any $f$.
\end{definition}

To make sure that an arbitrary table is folded we access the
table as follows.  For each pair $(f,-f)$ we choose (in some arbitrary
but fixed way) one representative.  If $f$ is chosen,
then if the value of the table is required at $f$ it is
accessed the normal way by reading $A(f)$.  If the value at $-f$ is
required then  in this case also $A(f)$ is read but the result
is negated.  If $-f$ is chosen from the pair the procedures are
reversed.

Similarly we can make sure that a given table
is properly conditioned by always reading $A(f\land h)$ when
the value for $f$ is needed.
Folding over true and conditioning can be done at the same
time.

Let us now give the consequences of folding and
conditioning for the Fourier coefficients.  The proofs
are easy and left to the reader but they can also
be found in \cite{h}.

\begin{lemma}\label{lem:folded}
If $A$ is folded over true and $\hat A_\alpha\not =0$ then
$|\alpha|$ is odd and in particular $\alpha$ is non-empty.
\end{lemma}

\begin{lemma}\label{lem:cond}
If $A$ is conditioned upon $h$ and $\hat A_\alpha\not =0$ then
for every  $x \in \alpha$, $h(x)$ is true (i.\,e., $h(x)=-1$). 
\end{lemma}

We will be working with sets $U$ and $W$ with the property
that $U\subset W$ and we let
$\pi : 
\{-1,1\}^W \to \{-1,1\}^U$ be the projection operator 
that maps an  
assignment on $W$ to its subassignment on $U$. For every 
$\beta \subseteq \{-1,1\}^W$, let $\pi(\beta) \subseteq 
\{-1,1\}^U$ be defined as 
 $$ \pi(\beta) = \{ \pi(y) \mid y \in \beta\}\enspace.
$$ 
We also need an operator $\pi_2$ defined as follows : for any 
$\beta \subseteq \{-1,1\}^W$, $\pi_2(\beta) \subseteq 
\{-1,1\}^U$ is the set of those $x$ which have an odd 
number of preimages in $\beta$, i.\,e.,
  $$ \pi_2(\beta) = \{ x \mid  x \in \{-1,1\}^U, \ 
    |\beta \cap \pi^{-1}(x)| \ \mbox{is \ odd}     \}\enspace.$$ 
Note that these projection operators depend on
the identities of $U$ and $W$ but as no confusion is likely
to arise we suppress this fact.

A function $f$ with domain $\{ -1, 1\}^U$ can naturally
be extended to domain $\{ -1, 1\}^W$ by simply
using the value $f(\pi(y))$.  We use the same symbol
to denote this extended function and hope that no
confusion arises.  We have the following simple
lemma.

\begin{lemma}\label{lem:projection}
Let $\beta \subseteq \{-1,1\}^W$, $U \subseteq W$
and $f : \{-1, 1\}^ U \to \{ -1,1\}$, then
$$
\chi_{\beta} (f) = \chi_{\pi_2(\beta)} (f)\enspace.
$$
\end{lemma}

\section{Efficient PCPs for Boolean domains}\label{sec:Boolean}

In this section we convert 2PP$(u)$ to a PCP.
We eliminate the provers by asking the prover to
write down the answer to each question (in encoded form). 
 Furthermore,
remember that $U$ is the set 
of $u$ variables which are
sent to $P_2$ in the two-prover protocol.  For each
possible set $U$ we ask the prover to write a table,
$A_U$, which is supposed to be the long code of
the answer by $P_2$ on question $U$.
We assume that $A_U$ is folded over true.

Similarly $W$ is the set of variables in the
$u$ clauses sent to $P_1$ and let $\varphi_W$ be the conjunction
of the clauses chosen.  In the PCP we have a table, $B_W$, which
is a supposed to be the long
code of the answer of $P_1$ on question $W$.
We assume that $B$ is
folded over true and conditioned upon $\varphi_W$.

\subsection{Our basic test}\label{sec:basic}

We have the following basic test, defined using
the conventions above.

\medskip
\noindent
\textbf{Basic PCP}

\begin{enumerate}

\item $V$ chooses $U$, $W$ and $\varphi_W$ as in
2PP$(u)$.

\item $V$ chooses two functions $f$ and $f'$ 
on $U$ uniformly at random (i.\,e., $f,f' : \{-1,1\}^U \to \{-1,1\}$). 

\item $V$ chooses two functions $g$ and $g'$ on
$W$ uniformly at random (i.\,e., $g,g' : \{-1,1\}^W \to \{-1,1\}$).  
$V$ defines a third function
$h$ by setting, for each
$y \in \{ -1,1\}^W$, $h(y)=g(y)f(\pi(y))(g'(y) \land f'(\pi (y)))$.

\item $V$ accepts iff $B_W(h)=B_W(g)A_U(f)(B_W(g') \land A_U(f'))$.

\end{enumerate}

We have the basic completeness lemma.

\begin{lemma} The completeness of the basic PCP is 1.
\end{lemma}

\begin{proof}
In a correct proof of a correct theorem each table
is a correct long code of a restriction
of a given global assignment to the set in
question.  If we denote this assignment by $z$ then
$B_W(h)=h(\pi^W(z))$ where $\pi^W$ is the projection
onto $W$ and similarly for the other involved functions.
The completeness now follows from the definition of $h$.
\end{proof}

The main problem is to establish soundness.

\begin{lemma} \label{lem:basic test} If the verifier in the basic test accepts
with probability $(1+\delta)/2$ then there exists
a strategy for $P_1$ and $P_2$ in 2PP$(u)$
that makes the verifier accept with probability
$\delta^{O(1)}$. In particular if the protocol 2PP($u$) is chosen to have 
sufficiently small soundness (by choosing $u$ large enough), then the 
verifier in the basic test accepts with probability at most $(1+\delta)/2$. 
\end{lemma}

\begin{proof}
For readability we drop the subscripts and
use $A$ instead of $A_U$ and $B$ instead of $B_W$.
Consider the expression 
$$
\frac{1+ B(h) B(g) A(f)(B(g') \land A(f'))  }{2}\enspace.  
$$ 
This expression is $1$ if the test accepts and $0$ otherwise. Hence the probability 
of acceptance for the test is the expectation of this expression over the choice of 
$f,f',g,g',U,$ and $W$.  The hypothesis of the lemma implies that
\begin{eqnarray}\label{eq extra accept}
E_{f,f',g,g',U,W} [B(h)B(g)A(f)(B(g') \land A(f'))] = \delta\enspace.
\end{eqnarray}
Fix $U,W, f'$ and $g'$ and let us study
$$
E_{f,g} [B(h)B(g)A(f)]\enspace.
$$
Replacing each function by its Fourier expansion we see that
this equals
$$
\sum_{\beta_1,\beta_2,\alpha}\hat B_{\beta_1} \hat B_{\beta_2}
\hat A_\alpha E_{f,g} [\chi_{\beta_1} (fg (f' \land g'))
\chi_{\beta_2} (g) \chi_{\alpha} (f)]
$$
which, using \eqref{eq alpha prod} and \lemref{lem:projection},
can be simplified to 
\begin{eqnarray}\label{equ1}
\sum_{\beta_1,\beta_2,\alpha}\hat B_{\beta_1} \hat B_{\beta_2}
\hat A_\alpha E_{f,g} [\chi_{\beta_1}( f' \land g')
\chi_{\beta_1 \oplus \beta_2}(g) \chi_{\pi_2(\beta_1) \oplus \alpha} (f)]\enspace.
\end{eqnarray}
Using \lemref{lem:exp chi}, the inner expected value is 0 unless
$\beta_1=\beta_2=\beta$ and $\pi_2(\beta)=\alpha$ and otherwise it is 1. Thus the
expected value in \eqref{equ1} equals
$$
\sum_\beta \hat B_\beta^2 \hat A_{\pi_2(\beta)} \chi_\beta (f' \land g')\enspace,
$$
and hence we need to analyze
\begin{eqnarray}\label{equ2}
E_{f',g'}[\chi_\beta (f' \land g')(B(g') \land A(f'))]\enspace.
\end{eqnarray}
We have  $a \land b = \frac 12 (1+a+b-ab)$ and thus \eqref{equ2}
equals
\begin{eqnarray}\label{eq 4 terms}
\frac 12 \left( E[\chi_\beta (f' \land g')]+
E[\chi_\beta (f' \land g')B(g') ]+
E[\chi_\beta (f' \land g')A(f')]-
E[\chi_\beta (f' \land g')B(g')A(f')] \right)\enspace.
\end{eqnarray}
Fix the value of $f'$ and let
$$
\beta'= \{ y\ |\ y \in \beta\ \land \  f'(\pi( y))=-1\}\enspace.
$$
When averaging over $g'$,  the first and third expected
values in \eqref{eq 4 terms}
are 0 unless $\beta' = \emptyset$ while the
second and the fourth expected values equal 
$\hat B_{\beta '}$ and $\hat B_{\beta '} A(f')$,
respectively.  To estimate the first and third
terms we note that the probability, over the choice of $f'$,
that $\beta'$ is empty is $2^{-| \pi (\beta) |}$.
For the other terms we set
$$
\alpha= \{ x\ |\ x \in \pi(\beta) \ \land \  f'(x)=-1\}
$$
and use the Cauchy-Schwarz inequality to obtain      
\begin{eqnarray}\label{eq cs standard}
E_{f'}\left[ | \hat B_{\beta'}| \right] = 2^{-| \pi (\beta)|}
\sum_{\alpha \subseteq \pi(\beta)} | \hat B_{\beta \cap \pi^{-1}(\alpha)}|
 \leq 2^{-| \pi (\beta)|/2}
\left(
\sum_{\alpha \subseteq \pi(\beta)}  \hat B^2_{\beta \cap \pi^{-1}(\alpha)}
\right)^{1/2}
 \leq 2^{-| \pi (\beta)|/2}\enspace. 
\end{eqnarray}
This implies that we get an overall upper bound on  
the left hand side of \eqref{eq extra accept} as
\begin{eqnarray}\label{eq pi sum}
E_{U,W}\left[\sum_\beta \hat B_\beta^2 |\hat A_{\pi_2(\beta)}| 
(2^{-|\pi (\beta) |}+2^{-|\pi (\beta) |/2})\right] \leq
E_{U,W}\left[\sum_\beta \hat B_\beta^2 |\hat A_{\pi_2(\beta)}| 
2^{1-|\pi (\beta) |/2}\right],
\end{eqnarray}
and hence this expression is at least $\delta$.  We use this to establish
good strategies for $P_1$ and $P_2$.  We first establish that some
parts of the given sum are small.  We have the following result from
\cite[Lemma 6.9]{h}
\begin{eqnarray}\label{eq size pi}
E_U\bigl[|\pi (\beta)|^{-1}\bigr] \leq |\beta|^{-c}\enspace,
\end{eqnarray}
where $c$ is a constant and in fact $c=\frac {1}{35}$
is possible.
Note that the expectation is taken only over $U$ and
is true for any $W$.

Let $S_\delta =  (4(6+2\log {\delta^{-1}})/\delta)^{1/c}$
and consider any $\beta$ of size at least  $S_\delta$.
Since 
$$
E[ |\pi (\beta) | ^{-1} ] \leq \delta/4(6+2\log {\delta^{-1}})^{-1} \enspace,
$$ 
we conclude that the probability that 
$| \pi (\beta) | \leq (6+2 \log {\delta^{-1}})$ is upper bounded
by $\delta/4$.
Thus for any $\beta$ of size at least $S_\delta$ we have
$$
E_U [2^{1-|\pi (\beta)|/2}] \leq 
Pr[ |\pi (\beta)| \leq (6+2\log \delta^{-1})]+ 2^{2+\log \delta^{-1} }\leq
\frac {\delta}{4}+\frac {\delta}{4} =
\frac {\delta}{2}
$$
and hence discarding terms with $|\beta| \geq S_\delta$
in \eqref{eq pi sum} still keeps a sum of expected
value at least $\delta/2$.

Furthermore since $\sum_\beta \hat B_\beta^2 =1$ we can discard
any term with $|\hat A_{\pi_2 (\beta)}| \leq \delta/4$ and
not reduce the sum by more than $\delta/4$.  We conclude that
the sum which is the right hand side of \eqref{eq pi sum}
is at least $\delta/4$ even if we restrict summation
to $\beta$ of size at most $S_\delta$ and such
that $|\hat A_{\pi_2 (\beta)}| \geq \delta/4$.

Now consider the following strategy for the provers $P_1$ and $P_2$.
On receiving $W$, $P_1$ chooses $\beta$ with probability
$\hat B_\beta^2$ and returns a random $y \in \beta$.  Similarly
on receiving a $U$, $P_2$ chooses $\alpha$ with probability
$\hat A_\alpha^2$ and returns a random $x \in \alpha$.
 We note that since $A, B$ are folded over true, by \lemref{lem:folded},
the sets $\alpha$ and
$\beta$ selected by the provers are always nonempty. Also, since $B$ is conditioned upon 
$\varphi_W$, by \lemref{lem:cond}, 
every $y \in \beta$ satisfies the formula $\varphi_W$.  
The success-probability of the given strategy is at least
\begin{eqnarray}\label{eq success 1}
E_{U,W} \left[\sum_\beta \hat B_\beta^2 \hat A_{\pi_2(\beta)}^2 |\beta|^{-1}\right]\enspace.
\end{eqnarray}
If we restrict summation to $|\beta | \leq S_\delta$ and 
$|\hat A_{\pi_2(\beta)}| \geq \delta/4$, \eqref{eq success 1}
is at least
$$
S_\delta^{-1} \delta/4  \ 
E_{U,W} \left[\sum_{\beta ; |\beta|\leq S_\delta , 
 |\hat A_{\pi_2(\beta)}| \geq \delta/4} \hat B_\beta^2 |\hat A_{\pi_2(\beta)}| \right]
$$
and, by the above reasoning, this expected value is at
least $\delta/4$ and we get a lower bound
$S_\delta^{-1} (\delta/4)^2$ for the success probability of 
the provers.  This completes the proof of \lemref{lem:basic test}.
\end{proof}

The basic test reads 5 bits $(b_1,b_2,b_3,b_4,b_5)$
of the proof and checks whether $b_1b_2b_3(b_4 \land b_5)=1$ which 
is same as $b_1 = b_2 \oplus b_3 \oplus (b_4 \land b_5)$ in 
$\{0,1\}$ notation. 
\thmref{thm:max tsa} now follows by a standard 
procedure of replacing the bits in the proof by variables and 
asking for a proof that maximizes the acceptance probability. 

\subsection{Iterated tests} \label{sec:iterated binary}

We now extend our basic test in a query efficient way.
We pick one set $U$ and on it we pick $k$ functions
$(f_i)_{i=1}^k$ and $k$ functions $(f_j')_{j=1}^k$
and $k$ sets $(W_l)_{l=1}^k$ each with its pair
of functions $(g_l, g_l')$.  Each $W_l$ is picked
uniformly from the set of possible companion in 2PP$(u)$ to
the already picked $U$.  Thus for each $l$, $(U,W_l)$ appears
with the same probability as $(U,W)$ in 2PP$(u)$.  Note
that $W_l$ is not independent of $W_{l'}$ for $l\not= l'$ as they are
companions of the same $U$.

We perform
the basic test for a certain set of quadruples
$(f_i,f_j',g_l,g_l')$.  We give
strong analyses in two cases each utilizing
$k^2$ quadruples.  One is given by
the constraint $i=j$ and is analyzed very much as
Samorodnitsky and Trevisan \cite{st} analyzed their tests.
We call it the ``complete bipartite PCP''.

The other set of $k^2$ quadruples  is given by all
triples ($i,j,l$)  such that $i+j+l=0 \bmod k$.  The key
property of this set of triples is that any
two different triples have at most one coordinate
in common.  Hence we call it the ``almost disjoint sets PCP''.
This analysis, done in the style of H\aa stad
and Wigderson \cite{hw}, is substantially
simpler and hence we give this proof first.

In either case we get a test that reads $4k+k^2$ bits,
has perfect completeness and soundness only marginally
higher than $2^{-k^2}$. \thmref{thm:main}
can therefore be obtained either from 
\thmref{thm:almost disjoint} below which analyzes
the almost disjoint sets PCP or
\thmref{thm:graph test} which analyzes the
complete bipartite test.

\subsubsection{The almost disjoint sets PCP}

We first define the test which is an iteration
of the basic test studied in the last section.
The test depends on the parameter $u$ used in
2PP$(u)$ but we keep this dependence implicit to
simplify notation.

\bigskip
\noindent
textbf {{\em k}-iterated almost disjoint sets PCP}  

\begin{enumerate}

\item $V$ chooses $U$ as in 2PP$(u)$.

\item $V$ chooses independently $k$ sets $(W_l)_{l=1}^k$,
that can appear with $U$ in 2PP$(u)$.  Each $W_l$ is chosen
with the distribution induced by 2PP$(u)$, i.\,e., the
distribution of the pair $U,W_l$ is the same as the
distribution of $U,W$ in 2PP$(u)$.

\item $V$ chooses $2k$ functions $(f_i)_{i=1}^k$ and $(f'_j)_{j=1}^k$ 
on $U$ uniformly at random.

\item For each $l$, $1\leq l\leq k$,
 $V$ chooses two functions $g_l$ and $g'_l$ on
$W_l$ uniformly at random.

\item For each triple $i,j,l$ such that $i+j+l\equiv 0 \bmod k$
 define a function $h_{ijl}$ by setting for each
$y \in \{ -1,1\}^{W_l}$, $h_{ijl}(y)=g_l(y)f_i(\pi(y))(g'_l(y) \land f'_j(\pi (y)))$.

\item $V$ accepts iff $B_{W_l}(h_{ijl})=B_{W_l}(g_l)A_U(f_i)(B_{W_l}(g'_l) \land A_U(f'_j))$ for
all $i+j+l\equiv 0 \bmod k$.

\end{enumerate}

We have the following theorem.
\begin{theorem}\label{thm:almost disjoint}
The $k$-iterated almost disjoint sets test has completeness $1$ and
soundness $2^{-k^2}+d_c^{\Omega (u)}$, where $d_c$ is
the constant from \thmref{thm:2ppu} and $u$ is the
parameter of the underlying 2-prover protocol.
\end{theorem}

\begin{proof}
The completeness follows from that of the basic test and we need
to analyze the soundness.   For readability let us
replace $A_U$ by $A$ and $B_{W_l}$ by $B_l$. Let $Z_0$ denote the set 
of all triples $(i,j,l)$ such that $i+j+l \equiv 0 (\bmod k)$. 

Let $\Acc(i,j,l)$ be a variable that indicates whether
the test given by the triple $(i,j,l)$ accepts, 
taking the value 1 if it does and $-1$ otherwise.
Clearly
$$
\Acc(i,j,l)=B_{l}(h_{ijl}) B_{l}(g_l) A(f_i) (A(f_j') \land B_l(g_l'))\enspace.
$$
Consider
\begin{eqnarray}\label{mod 2 expansion}
\prod_{(i,j,l) \in Z_0} \frac {1+\Acc(i,j,l)}{2} =
2^{-k^2} \sum_{S \subseteq Z_0} \prod_{(i,j,l) \in S}
\Acc(i,j,l)\enspace.
\end{eqnarray}
This number equals $1$ if the test accepts and is $0$ otherwise
and thus its expected value is the probability that the test
accepts.  The term in the right hand side sum
with $S= \emptyset$ equals 1 and to establish
the theorem it is sufficient to establish that any
other term is bounded by $d_c^{\Omega (u)}$.  Let $\Pi_S$ be
the term corresponding to $S\not=\emptyset$ and let $T_S$
be the expectation of $\Pi_S$.
We go on to establish strategies for $P_1$ and $P_2$ which
makes the verifier in 2PP$(u)$ accept with probability
$|T_S|^{O(1)}$.  This is clearly sufficient to establish
the theorem.

Suppose without loss of generality that $(k,k,k) \in S$ and let us fix
the values of $f_i$, $i\not= k$, $f_j'$, $j\not= k$
and $(W_l, g_l, g_l')$ for $l\not= k$ in such a way
that the conditional expectation of $\Pi_S$ remains
at least $T_S$.  As the sets in $Z_0$
only intersect in one point we can, up to a factor $\pm 1$, write $\Pi_S$ as
\begin{eqnarray}\label{ts prod}
\Acc(k,k,k) \prod_{(k,j,l) \in S, j,l\not= k} \Acc(k,j,l)
\prod_{(i,k,l) \in S, i,l\not= k} \Acc(i,k,l)
\prod_{(i,j,k) \in S, i,j\not= k} \Acc(i,j,k)
\end{eqnarray}
as the rest of the variables are fixed.  The three products
of \eqref{ts prod}
can be written as $A^{(1)}(f_k)$, $A^{(2)}(f'_k)$ and
$B^{(1)}(g_k,g_k')$ respectively, for some Boolean functions
$A^{(1)}$, $A^{(2)}$ and $B^{(1)}$.  

Expanding the definition of $\Acc(k,k,k)$ and using
$x \land y = \frac {1+x+y-xy}{2}$ for 
$A(f_k') \land B_{k}(g'_{k})$ we see that
\eqref{ts prod} can 
be written as the sum  of four terms of  the form
\begin{eqnarray}\label{ad term}
B_k(h_{kkk}) A'(f_k)A''(f_k')C(g_k,g_k')\enspace,
\end{eqnarray}
each with a coefficient $1/2$, for some Boolean functions
$A'$, $A''$ and $C$ closely related to $A^{(1)}$, $A^{(2)}$ and
$B^{(1)}$.  To be more precise 
$$
A'(f_k)=A(f_k)A^{(1)}(f_k)\enspace,
$$
$$
A''(f'_k)=A^{(2)}(f'_k) \quad \mbox{or} \quad
A''(f'_k)=A(f'_k) A^{(2)}(f'_k)\enspace,
$$
and
$$
C(g_k,g'_k)=B_k(g_k) B^{(1)}(g_k,g'_k) \quad \mbox{or} \quad
C(g_k,g'_k)=B_k(g_k) B_k(g_k') B^{(1)}(g_k,g'_k)\enspace.
$$

We want to prove that if the expectation of \eqref{ts prod}
is large then the provers $P_1$ and $P_2$ in the
two prover game can convince the verifier of that
protocol to accept with high
probability.  To this end we use the tables in
the given PCP to construct strategies for $P_1$ and
$P_2$.  We need to be slightly careful since not
all derived tables can be used by a given prover
as it might depend on information not available
to this particular prover.

In the present situation
the functions $A'$ and $A''$ depend only on $U$ and
the fixations made and hence are available for player $P_2$
to design a strategy.  $B_k$ is the original long code on $W_k$
and hence is useful for extracting a strategy for $P_1$.
Finally $C$ is a function that depends
on both $U$ and $W_k$ and as this is not fully known to
either $P_1$ or $P_2$, $C$ is not useful for designing
strategies.

Since we only have one remaining object of each type, 
let us for readability discard the index replacing $f_k$ by
$f$, $W_k$ by $W$, etc.  

We now want to compute the expected value of \eqref{ad term}
over random choices of $f$, $f'$, $g$ and $g'$.
Expanding all factors except $A''(f')$ by the Fourier transform we get
\begin{eqnarray}\label{eq abc1}
\sum_{\alpha, \beta,\gamma, \gamma'} \hat A'_\alpha
\hat B_\beta \hat C_{\gamma, \gamma'} 
E_{f,f',g,g'}\left[\chi_\alpha (f) \chi_\beta(gf(f'\land g') )
\chi_{\gamma}(g)\chi_{\gamma'}(g')A''(f')\right]\enspace.
\end{eqnarray}
Taking the expectation over $f$ we see, using
\lemref{lem:exp chi}, that any term with
$\alpha \not= \pi_2(\beta)$ vanishes while
if we have equality the expectation is 1.  Similarly,
considering the expectation over $g$, we see that only terms
with $\beta=\gamma$ give a nonzero contribution.
Finally, fixing $f'$ and considering expectation over $g'$,
we see that only terms with $\gamma' = \beta \cap 
\pi^{-1}(f'^{-1}(-1))$ remain nonzero.

This implies that \eqref{eq abc1} reduces to
\begin{eqnarray}\label{eq abc2}
E_{U,W,f'}\left[\sum_{\beta} \hat A'_{\pi_2(\beta)}
\hat B_\beta \hat C_{\beta,\beta\cap \pi^{-1}(f'^{-1}(-1))} A''(f')\right]
\end{eqnarray}
and, fixing $U$ and $W$, let us estimate
\begin{eqnarray}\label{eq abc2 f'}
E_{f'}\left[\sum_{\beta} \hat A'_{\pi_2(\beta)}
\hat B_\beta \hat C_{\beta,\beta\cap \pi^{-1}(f'^{-1}(-1))} A''(f')\right].
\end{eqnarray}
Towards this end we have
\begin{eqnarray}
 | \ E_{f'}[ \hat C_{\beta, \beta\cap \pi^{-1}(f'^{-1}(-1))} A''(f')] \ | 
 \ & \leq &  \ E_{f'}[|\hat C_{\beta , \beta\cap
 \pi^{-1}(f'^{-1}(-1))}|]  \ \leq \\ \nonumber
2^{-|\pi (\beta)|} \sum_{\alpha' \subseteq \pi(\beta)}
|\hat C_{\beta , \beta \cap \pi^{-1}(\alpha')}| \ & \leq & \ 
2^{-|\pi (\beta)|/2} \left(\sum_{\alpha' \subseteq \pi(\beta)}
\hat C_{\beta , \beta \cap \pi^{-1}(\alpha')}^2\right)^{1/2}. \nonumber
\end{eqnarray}
Substituting this estimate into \eqref{eq abc2 f'} we get
the upper estimate
\begin{eqnarray}
\sum_{\beta} \vert \hat A'_{\pi_2(\beta)}
\hat B_\beta \vert 
2^{-|\pi (\beta)|/2} \left(\sum_{\alpha' \subseteq \pi(\beta)}
\hat C_{\beta , \beta \cap \pi^{-1}(\alpha')}^2\right)^{1/2}
\end{eqnarray}
and applying the Cauchy-Schwarz inequality over $\beta$ this   
is bounded by
\begin{eqnarray}
\left( \sum_\beta \hat B_\beta^2 \hat A'^2_{\pi_2(\beta)}
2^{-|\pi (\beta)|} \right)^{1/2}
\left( \sum_{\beta,\beta_1} \hat C_{\beta,\beta_1}^2 \right)^{1/2}
\leq
\left( \sum_\beta \hat B_\beta^2 \hat A'^2_{\pi_2(\beta)}
2^{-|\pi (\beta)|} \right)^{1/2},
\end{eqnarray}
which is our final upper bound 
for the absolute value of the expectation of $\Pi_S$
when $U$ and $W$ are fixed.
As $E[X^2] \geq E[X]^2$ we have
\begin{eqnarray*}
E_{U,W} \left[ \sum_\beta \hat B_\beta^2 \hat A'^2_{\pi_2(\beta)}
2^{-|\pi (\beta)|} \right] \geq
E_{U,W}\left[| E_{f,f',g,g'} [\Pi_S]|^2 \right] 
\geq
E_{U,W}\left[| E_{f,f',g,g'} [\Pi_S]| \right] ^2
\geq
E[\Pi_S]^2 \geq T_S^2\enspace.
\end{eqnarray*}

The rest of the proof now follows along the same lines
as end of the proof for the basic test.  In that proof
we had established that the right hand side of \eqref{eq pi sum}
was large and used this to derive strategies for the provers.  We now
have proved that a very similar sum is large.  The fact
that we have replaced $\hat A_{\pi_2(\beta)}$ by $\hat A_{\pi_2(\beta)}'^2$
 is only to our advantage.  As $A'$ is a derived table we
cannot make sure that it is folded over true and thus
when $P_2$ picks $\alpha$ with probability $\hat A_{\alpha}'^2$
the set $\alpha$ might be empty.  In this case
$P_2$ might return any assignment and we assume that the
verifier rejects in this case.  This does not disturb
the analysis as $B$ is folded over true and hence $|\beta|$
is odd which implies that $\pi_2 (\beta)$ is nonempty.
\end{proof}

\subsubsection{The bipartite graph test}

In this section we study the following test.

\medskip
\noindent
\textbf{{\em k}-iterated bipartite graph PCP}

\begin{enumerate}

\item $V$ chooses $U$ as in 2PP$(u)$.

\item $V$ chooses independently $k$ sets $(W_l)_{l=1}^k$,
that can appear with $U$ in 2PP$(u)$.  Each $W_l$ is chosen
with the distribution induced by 2PP$(u)$, i.\,e., the
distribution of the pair $U,W_l$ is the same as the
distribution of $U,W$ in 2PP$(u)$.

\item $V$ chooses $2k$ functions $(f_i)_{i=1}^k$ and $(f'_i)_{i=1}^k$ 
on $U$ uniformly at random.

\item For each $l$, $1\leq l\leq k$,
 $V$ chooses two functions $g_l$ and $g'_l$ on
$W_l$ uniformly at random.

\item For each pair $i,l$ 
 define a function $h_{il}$ by setting for each
$y \in \{ -1,1\}^{W_l}$, 
$$
h_{il}(y)=g_l(y)f_i(\pi(y))(g'_l(y) \land f'_i(\pi (y)))\enspace.
$$

\item $V$ accepts iff $B_{W_l}(h_{il})=B_{W_l}(g_l)A_U(f_i)(B_{W_l}(g'_l) \land A_U(f'_i))$ for
all $1\leq i,l \leq k$.

\end{enumerate}
We have the following theorem.

\begin{theorem}\label{thm:graph test}
The bipartite graph test has completeness $1$ and
soundness $2^{-k^2}+d_c^{\Omega (u)}$.
\end{theorem}

\begin{proof}
The completeness is again not difficult and we leave it the
reader to verify that indeed $V$ always accepts a correct
proof for a correct statement.

In the analysis of the soundness let us use notation
similar to the one used in the previous proof, e.g., writing
$B_l$ instead of $B_{W_l}$ and $A$ instead
of $A_U$.  Also define
$$
\Acc(i,l)=
B_{l}(h_{il}) B_{l}(g_l) A(f_i) (A(f_i') \land B_l(g_l'))\enspace,
$$
which is 1 if the test involving
$h_{il}$ accepts and $-1$ if the test fails.
Now we want to calculate the expected value of
\begin{eqnarray}\label{eq il prod}
\prod_{(i,l) \in [k]\times [k]  } \frac {1+\Acc(i,l)}{2} 
= 2^{-k^2} \sum_{S \subseteq [k]\times [k]} \prod_{(i,l)\in S}
\Acc(i,l)\enspace.
\end{eqnarray}
Let $T_S$ be the expectation of the 
product for $S$ and the goal is again to,
for any nonempty set $S$,  give a prover-strategy with
success rate $|T_S|^{O(1)}$.  We start by, as already
done in \cite{st},  reducing to the case
of special $S$ and let $T_{2d}$ be the result when $S$
is the edge set of the complete bipartite graph on $[2]\times [d]$.

\begin{lemma}[\cite{st}]
For any nonempty $S$, there is an integer $d$ such that
$ |T_S| \leq |T_{2d}|^{1/2}$.
\end{lemma}

\begin{proof}
As all coordinates are treated symmetrically
me may, without loss of generality, assume that $(1,1) \in S$ and
that $(1,2), \ldots (1,d)$ are the other vertices in $S$ connected
to 1.  Let us divide our random choice of 
$(f_i,f_i',g_l,g_l')_{i,l=1,\ldots,k}$ into $X$ given by choice of $(f_1,f_1')$,
and $Y$ given by choice of the rest.  Let $S_1$ be
the subset of $S$ given by $(1,1),(1,2) \ldots (1,d)$. Then
\begin{eqnarray*}
E_{X,Y} [\prod_{(i,l) \in S} \Acc(i,l)]=
E_{X,Y} [ \prod_{l=1}^d \Acc(1,l) \cdot  \prod_{(i,l) \in S \setminus S_1}
\Acc(i,l)] = \\
E_{X,Y} [F(X,Y) G(Y)] = E_Y [ E_X[F(X,Y)] G(Y)] 
\end{eqnarray*}
for some functions $F$ and  $G$ with values in $\{-1,1\}$.  Now applying 
the Cauchy-Schwarz inequality this can be bounded by       
\begin{eqnarray*}
 \sqrt{E_Y [ (E_X[F(X,Y)])^2]}
\sqrt{E_Y[G(Y)^2]}
 & \leq & \sqrt{E_Y [ (E_X[F(X,Y)])^2]} = \\
\sqrt{E_Y [E_{X_1}[F(X_1,Y)] \cdot 
E_{X_2}[F(X_2,Y)]]} & = & \sqrt{E_{X_1,X_2,Y}[F(X_1,Y)\cdot F(X_2,Y)]}
\end{eqnarray*}
where $X_1, X_2$ are identically distributed as $X$ and are
independent. The proof is completed by
the observation that $F(X_1,Y)\cdot F(X_2,Y)$ 
is equal to   $\prod_{l=1}^d \Acc(1,l) \cdot \prod_{l=1}^d
\Acc(2,l)$, which is exactly the same as $T_{S'}$ where $S'$ is  
a complete bipartite graph on $[2] \times [d]$. 
\end{proof}

Thus it is sufficient to find a good strategy based
on $|T_{2d}|$ being large.  Using the definition of Acc and canceling 
the factors $B_l(g_l)$
that appears exactly twice, we have
\begin{eqnarray}\label{eq t2d}
T_{2d} = E \left[ \ \prod_{l=1}^d  B_l(h_{1l}) B_l(h_{2l})
  A(f_1)A(f_2)(A(f_1')A(f_2') \land B_l(g_l')) \right]\enspace.
\end{eqnarray}
The function
$g_l$ affects $T_{2d}$ only through $h_{1l}$
and $h_{2l}$ and replacing $B_l(h_{1l})$ and $B_l(h_{2l})$
by their Fourier expansions we see that
\begin{eqnarray} 
E_{g_l} [B_l(h_{1l}) B_l(h_{2l})] & = & \nonumber
\sum_{\beta_1, \beta_2} \hat B_{l,\beta_1} \hat B_{l,\beta_2}
E_{g_l} [\chi_{\beta_1} (g_l f_1 (g_l'\land f_1'))
\chi_{\beta_2} (g_l f_2 (g_l'\land f_2'))]= \\  
&& \sum_\beta \hat B_{l,\beta}^2 \chi_\beta (f_1f_2) 
\chi_\beta(f_1'f_2' \land g_l')\enspace. \label{eq bbexpect}
\end{eqnarray}
Substituting this into \eqref{eq t2d}
we get
\begin{eqnarray}\label{eq mess1}
E \left[ \ \prod_{l=1}^d  \left( \sum_{\beta_l} 
\hat B_{l,\beta_l}^2 \chi_{\beta_l} (f_1f_2) 
\chi_{\beta_l}(f_1'f_2' \land g_l')\right)
 A(f_1)A(f_2)((A(f_1')A(f_2')) \land B_l(g'_l))\right]\enspace.
\end{eqnarray}

Let us now consider the expectation over $f_1$ and $f_2$.
If $d$ is even then the dependence of \eqref{eq mess1} on
$f_1$ and $f_2$ is of the form
$$
\prod_{l=1}^d \chi_{\beta_l} (f_1f_2)\enspace.
$$
which has expected value 0 unless $\oplus_j \pi_2(\beta_l)=\emptyset$
while the expectation is 1 if we have equality.

If $d$ is odd, then the dependence of $f_1$ and $f_2$ is
of the form
$$
A(f_1)A(f_2) \prod_{l=1}^d \chi_{\beta_l} (f_1f_2)\enspace.
$$
Replacing $A(f_1)$ and $A(f_2)$ by
their Fourier expansions we see that the expectation
of this with respect to $f_1$ and $f_2$ equals
$\hat A^2_\alpha$ where
$$
\alpha = \oplus_l \pi_2 (\beta_l)\enspace.
$$

Now let us turn to analyzing the rest of \eqref{eq mess1}.
First note that
$$
\prod_{l=1}^d (A(f_1')A(f_2') \land B_l(g_l'))=
(A(f_1')A(f_2') \land \prod_{l=1}^d B_l(g_l'))\enspace.
$$
We have $(x\land y) = \frac{1+x+y-xy}{2}$ and 
we are now ready to consider the expectation
over $f_1'$ and $f_2'$ and $g_l'$.
We have expressions of the form
\begin{eqnarray}\label{eq abb}
(A(f_1')A(f_2'))^a
\prod_{j=l}^d \chi_{\beta_l}(f_1'f_2' \land g_l') ( \prod_{l=1}^d B_l(g_l'))^b\enspace,
\end{eqnarray}
for $a,b \in \{ 0,1\}$.
Now, view 
$$
C(g_1',g_2' \ldots g_d')
=(\prod_{l=1}^d B_l(g_l'))^b
$$
as a Boolean function with
Fourier coefficients $\hat C_{\gamma_1,\gamma_2,. \ldots \gamma_d}$,
and thus \eqref{eq abb} equals
\begin{eqnarray}\label{eq abb2}
\sum_{\gamma_1, \gamma_2, \ldots \gamma_l} (A(f_1')A(f_2'))^a \hat C_{\gamma_1,\gamma_2,. \ldots \gamma_d}
\prod_{j=l}^d \chi_{\beta_l}(f_1'f_2' \land g_l') \chi_{\gamma_l}(g_l')\enspace.
\end{eqnarray}

Let $\alpha'=\cup_{l=1}^d \pi (\beta_l)$.
For a fixed choice of $f_1'f_2'=f'$ we get a nonzero expected
value over $(g_l')_{l=1}^d$  iff $\gamma_l 
= \beta_l \cap \pi^{-1}(f'^{-1}(-1))$
for all $l$, giving a unique non-zero term.  Defining
$\gamma_l^{\vec \beta, f'}$ to be this value we get
\begin{eqnarray}
\left| E_{f_1',f_2',g_1', g_2', \ldots g_d'}\left[
(A(f_1')A(f_2'))^a
\prod_{j=l}^d \chi_{\beta_l}(f_1'f_2' \land g_l') 
( \prod_{l=1}^d B_l(g_l'))^b\right] \right| & \leq & \\
\left| E_{f_1',f_2'}\left[
\hat C_{\gamma_1^{\vec \beta, f'} ,\gamma_2^{\vec \beta, f'}
,. \ldots \gamma_d^{\vec \beta, f'}} \right] \right|
& \leq  & 2^{-|\alpha'|/2}\enspace,
\end{eqnarray}
where the last inequality follows from the Cauchy-Schwarz inequality   
using a similar calculation to that in \eqref{eq cs standard}.
This means that in the case when $d$ is even we get the
upper estimate
\begin{eqnarray} \label{eq even case}
\sum_{\oplus_l \pi_2(\beta_l)=\emptyset} \prod_{l=1}^d \hat B_{l,\beta_l}^2 2^{-|\alpha'|/2}
\end{eqnarray}
for $|T_{2d}|$ while in the case when $d$ is odd we get
\begin{eqnarray} \label{eq odd case}
\sum
\hat A_{\oplus_l \pi_2(\beta_l)}^2
\prod_{l=1}^d \hat B_{l,\beta_l}^2 2^{-|\alpha'|/2}\enspace,
\end{eqnarray}
where in both cases we have $\alpha' = \cup_{l=1}^d \pi(\beta_l)$.

Strategies for the provers can now be defined as follows.
$P_1$ upon receiving $W$, picks $\beta$ with probability
$\hat B_\beta^2$ and returns a random $y\in \beta$.
$P_2$ upon receiving $U$ picks $d-1$ random $W_l$, $l=2 \ldots d$
and picks $\beta_2, \ldots \beta_d$ with probability 
$\prod_{l=2}^d \hat B_{l,\beta_l}^2$ and computes $\alpha''=\oplus_{l=2}^d
\pi_2( \beta_l)$.  If $d$ is even $P_2$ returns a random
$x \in \alpha''$.  If $d$ is odd $P_2$ also picks $\alpha$
with probability $\hat A_\alpha^2$ and returns a random element
in $\alpha'' \oplus  \alpha$.  Note that by folding, in both cases
the defined set is of odd cardinality and hence is not
empty.

The probability of success is, in
the case of even $d$, at least
\begin{eqnarray} \label{eq even case accc}
\sum_{\oplus_l \pi_2(\beta_l)=\emptyset} \prod_{l=1}^d \hat
B_{l,\beta_l}^2 
(\sum |\beta_l|)^{-1}
\end{eqnarray}
and in the case of odd $d$ it as at least
\begin{eqnarray} \label{eq odd case accc}
\sum \hat A_{\oplus_l \pi_2(\beta_l)}^2 \prod_{l=1}^d \hat
B_{l,\beta_l}^2 
(\sum |\beta_l|)^{-1}\enspace.
\end{eqnarray}
Using \eqref{eq size pi} these probabilities
can be related
to expressions \eqref{eq even case} and \eqref{eq odd case} in
a way similar to the basic proof case.  We omit the
details.  The result is that
the verifier in 2PP$(u)$ accepts with probability
$|T_{2d}|^{O(1)}$ and the theorem follows.
\end{proof}

\subsubsection{Adaptive tests}

In this section we prove \thmref{thm:adaptive}
by defining a suitable adaptive test.  The theorem then
follows from analyzing the completeness, which
is done in \lemref{lem:complete adaptive}
and the soundness which is done in 
\lemref{lem:sound adaptive}
Guruswami et al. \cite{glst} give an adaptive test
reading three bits that has perfect completeness and
soundness $\frac 12 + \epsilon$ for any $\epsilon > 0$.
The non-adaptive version of this test has the same
parameters except that it reads 4 bits.  The natural
iterated test based on this test reads $2k+k^2$ bits
in the adaptive setting and $2k+2k^2$ bits in the non-adaptive
setting.  It has perfect completeness and it turns out
that soundness is essentially $2^{-k^2}$ also
for this test.

Thus its parameters, when adaptive, are the same as
those of the test of Samorodnitsky and Trevisan while
achieving perfect completeness.  As sketched in
\cite{hk}, this test can be
designed and analyzed with the same basic two-prover
protocol as the previous tests but the construction
turns out to be technically simpler if we modify the
two-prover protocol.  We do this to obtain
the property
called ``smoothness'' in \cite{k33}.  We need that
for two different answers by $P_1$,  with high probability
the answers by $P_2$ causing acceptance are also
different.  This is achieved by sending a large number
of identical clauses to both provers.

\medskip
\noindent
\textbf{{\em u}-parallel two-prover protocol with 
redundancy factor {\em T}, 2PPe(\,\em{u,T}\,)}                           

\begin{enumerate}
\item $V$ chooses $Tu$ clauses $(C_{k_i})_{i=1}^{Tu}$ uniformly at
 random. Then he randomly selects $u$ clauses $(C_{j_i})_{i=1}^u$ 
out of these $Tu$ clauses 
and randomly selects a variable $x_{j_i}$ from each clauses $C_{j_i}$.  
He sends $({k_i})_{i=1}^{Tu}$ to prover $P_1$; and 
to prover $P_2$, he sends the $u$ chosen variables $(x_{j_i})_{i=1}^u$   
together with the $(T-1)u$ clauses not selected. 

\item $V$ receives values for the $u$ chosen variables      
$(x_{j_i})_{i=1}^u$ from $P_2$ as well as $3(T-1)u$ values
for the variables in the clauses sent to $P_2$.  $V$ also
receives $3Tu$ values from $P_1$ to the variables in the
clauses sent to $P_1$.  $V$ accepts
if no two values are inconsistent and all the picked
clauses are satisfied.
\end{enumerate}

We again call the sets of variables sent to  the two provers
$U$ and $W$, respectively. Note that this time
 $U$ is of size $u(3T-2)$ and $W$ is of
size $3uT$ while as before we have $U\subset W$.
Note also that for each fixed set of $(T-1)u$ clauses sent
to both players, we have an instance of the 2PP$(u)$.  This implies
that the soundness of 2PPe$(u,T)$ is at most that of 2PP$(u)$
and in particular it is upper bounded by $d_c^u$.

We now describe the PCP.  It depends on the parameters $u$ and $T$
but has also additional parameters $k$ and $\epsilon$.
For notational convenience we suppress the former.  

\medskip
\noindent
\textbf{{\em k}-iterated non-adaptive PCP of bias} $\mathbf{\epsilon}$ 

\begin{enumerate}

\item $V$ chooses $U$ as in 2PPe$(u,T)$.

\item $V$ chooses independently $k$ sets $(W_j)_{j=1}^k$,
that can appear with $U$ in 2PPe$(u,T)$.  Each $W_j$ is chosen
with the distribution induced by 2PPe$(u,T)$, i.\,e., the
distribution of the pair $U,W_j$ is the same as the
distribution of $U,W$ in 2PPe$(u,T)$.

\item $V$ chooses $k$ functions $(f_i)_{i=1}^k$ on $U$ uniformly at
  random and reads the bits $A_U(f_i)$.

\item For each $j$, $1\leq j\leq k$,
 $V$ chooses a function $g_j$ on
$W_j$ uniformly at random and reads the bits $B_{W_j}(g_j)$.

\item For each pair $i,j$ 
 define a function $h_{ij}$ by setting, independently, for each
$y \in \{ -1,1\}^{W_j}$, $h_{ij}(y)=-1$ with probability $1-\epsilon$
and otherwise $h_{ij}(y)=1$.

\item For each pair $i,j$, if $A(f_i)=1$, $V$ checks
that $B_j(g_j (f_i \land h_{ij}))=B_j(g_j)$ and otherwise
$V$ checks that $B_j(g_j( -f_i \land h_{ij}))=B_j(g_j)$.

\item $V$ accepts if all tests accept.
\end{enumerate}

Completeness is straightforward.
\begin{lemma}  \label{lem:complete adaptive}
The adaptive $k$-iterated test with bias $\epsilon$, accepts
with probability 1, i.\,e, it has perfect completeness.
\end{lemma}

\begin{proof}
Fix an $i$ and a $j$.  Suppose that we have a correct proof of a correct
statement based on the global assignment
$z$.  If $A(f_i)=1$ then $f_i(\pi^U (z))=1$ and we have 
$$
B_j(g_j (f_i \land h_{ij}))=g_j(\pi^W (z)) (f_i(\pi^U(z)) 
\land h_{ij}(\pi^W(z))) = g_j(\pi^W(z))=B_j(g_j)\enspace.
$$
The case $A(f_i)=-1$ is similar.
\end{proof}

We next turn to soundness.
\begin{lemma}\label{lem:sound adaptive}
Suppose that $T \geq \epsilon^{-5}$
and we are given a proof that makes the verifier in the adaptive iterated
test with parameter $\epsilon$
accept with probability $2^{-k^2}+2\delta$ where $\delta > 6\epsilon$.
Then we can find
strategies for $P_1$ and $P_2$ in 2PPe$(u,T)$ that makes the
verifier of that protocol accept with probability at least
$\epsilon^2(\delta - 6 \epsilon)^2/2$.
\end{lemma}

\begin{proof}
The proof follows along  the same lines as the result for the
protocol with $k=1$ given in \cite{glst} which in  turn
is based on the proof that
3SAT is inapproximable for satisfiable instances in \cite{h}.

Let
\begin{eqnarray*}
\Acc(i,j)= \frac 12 \left(
(1+A(f_i))B_j (g_j) B_j(g_j (f_i \land h_{ij}))+
(1-A(f_i))B_j (g_j) B_j(g_j (-f_i \land h_{ij})) \right)\enspace,
\end{eqnarray*}
which is 1 if the test given by $(i,j)$ accepts and $-1$
otherwise.  We have an expansion like \eqref{eq il prod}
and by the assumption of the lemma
implies that we have a nonempty $S$ such that
\begin{eqnarray}\label{eq ij}
E\left[ \prod_{(i,j)\in S}
\Acc(i,j) \right] \geq 2 \delta\enspace.
\end{eqnarray}
As all coordinates are symmetric
we may assume that $(1,1) \in S$.  Now fix the values of $g_j$
and $f_i$ for $i,j \geq 2$ and $h_{ij}$ for $(i,j) \not=(1,1)$
to any constants without
decreasing the expected value obtaining
\begin{eqnarray}
E_{U,W_1,f_1,g_1,h_{11}}
\left[ \Acc(1,1)A^{(1)}(f_1) B^{(1)}(g_1) \right] \geq 2 \delta
\end{eqnarray}
for some Boolean functions $A^{(1)}$ and $B^{(1)}$.
Using the expression for Acc$(1,1)$ we get an expression
of the form
\begin{eqnarray}\label{eq abc}
A'(f_1) B(g_1 (f_1 \land h_{11})) C(g_1)
\end{eqnarray}
or
\begin{eqnarray}
A'(f_1) B(g_1 (-f_1 \land h_{11})) C(g_1)
\end{eqnarray}
whose expectation over the choice of $U$, $f_1$,
$W_1$, $g_1$ and $h_{11}$ is at least $\delta$.
Here $A'$, $B$ and $C$ are Boolean functions where $B$ is the original
$B_1$ and $A'$ is a function only depending on $U$.  Since $f$
is chosen with the same distribution as $-f$
we might as well study \eqref{eq abc} and let us drop
the subscripts for readability.
Replacing each function by its Fourier expansion, we get that
the expectation of \eqref{eq abc} equals
\begin{eqnarray}\label{eq abc expect}
E_{U,W,f,g,h}\left[\sum_{\alpha, \beta, \gamma}
\hat A'_\alpha \hat B_\beta \hat C_\gamma
\chi_\alpha (f) \chi_\beta (g (f \land h)) \chi_\gamma (g) \right]\enspace.
\end{eqnarray}
Taking expectation over $g$ we see that terms with $\beta \not= \gamma$
have expectation 0 and thus \eqref{eq abc expect} equals
\begin{eqnarray}\label{eq abc expect2}
E_{U,W}\left[ \sum_{\alpha, \beta}
\hat A'_\alpha \hat B_\beta \hat C_\beta
E_{f,h} \left[ \chi_\alpha (f) \chi_\beta ( (f \land h)) \right]\right]\enspace.
\end{eqnarray}
If $\alpha \not\subseteq
\pi(\beta)$ the expectation over $f$ yields 0 and thus we need to study 
\begin{eqnarray}\label{eq fh}
E_{f,h} [\chi_\alpha (f) \chi_\beta (f \land h)]
\end{eqnarray}
where $\alpha \subseteq \pi(\beta)$.  Using the definition
of the characters \eqref{eq fh} equals
\begin{eqnarray}\label{eq fh prod}
E_{f,h} \left[\prod_{x\in \alpha} \left(f(x) \prod_{y \in \beta \cap \pi^{-1}
(x)} (f(x) \land h(y))\right)
\prod_{x\in \pi(\beta) \setminus \alpha} \left(\prod_{y \in \beta \cap \pi^{-1}
(x)} (f(x)\land h(y))\right)\right]
\end{eqnarray}
and as the different $x$ behave independently we can analyze
each factor independently.  We have $f(x)=1$ with probability
$1/2$  and in this case 
$$
\prod_{y \in \beta \cap \pi^{-1}
(x)} \left(f(x) \land h(y))\right)=1\enspace,
$$
while while if  
 $f(x)=-1$, it has expectation over $h$ that
equals $(2\epsilon -1)^{s_x}$ where
$s_x = \vert \pi^{-1} (x) \cap \beta \vert$.  We conclude
that the expectation of \eqref{eq fh prod} equals
$$
\prod_{x\in \alpha \cap \pi (\beta)}(\frac 12(1-(2\epsilon-1)^{s_x}))
\prod_{x\in \pi (\beta)\setminus \alpha }(\frac 12 
(1+(2\epsilon-1)^{s_x}))\enspace,
$$
and defining this expression to be $p(\alpha, \beta)$, we conclude
that \eqref{eq abc expect2} equals
\begin{eqnarray} \label{eq abcfinal}
E_{U,W} \left[\sum_{\beta, \alpha \subseteq \pi(\beta)} \hat A'_\alpha \hat B_\beta
\hat C_\beta p(\alpha, \beta)\right]\enspace.
\end{eqnarray}
By assumption this expectation is
at least $\delta$ and we need to design strategies for $P_1$ and
$P_2$.

The strategies of the two provers are the standard strategies.  i.\,e.,
$P_2$ chooses an $\alpha$ with probability $\hat A'^2_\alpha$ and returns a
random $x\in \alpha$.  Similarly $P_1$ chooses a random $\beta$ with probability
$\hat B_\beta^2$ and returns a random $y \in \beta$.  Again $A'$ cannot be
assumed to be folded as it is a derived table.  If $\alpha$ is the empty
set we do not care what $P_2$ does and we assume in the analysis that
the verifier rejects.  The table $B$, on the other hand, is the
original table and hence $\beta$ is nonempty and any $y\in \beta$ satisfies the
selected clauses.  We conclude that the strategy of the provers is
successful with probability at least
\begin{eqnarray}\label{eq ss2}
E_{U,W} \left[ \sum_{\beta, \emptyset \not= \alpha \subseteq \pi( \beta)} \hat A'^2_\alpha
\hat B_\beta^2 |\beta|^{-1}\right]\enspace.
\end{eqnarray}
We need to prove that this is large based on \eqref{eq abcfinal} being
at least $\delta$.

First note that
\begin{eqnarray}\label{eq bc}
\sum_\beta |\hat B_\beta \hat C_\beta| \leq
\left( \sum_\beta \hat B_\beta^2 \right)^{1/2}
\left( \sum_\beta \hat C_\beta^2 \right)^{1/2}
\leq 1\enspace,
\end{eqnarray}
and the quantity that multiplies $\hat B_\beta \hat C_\beta$ 
in \eqref{eq abcfinal} satisfies
\begin{eqnarray}
\left\vert \sum_{\alpha \subseteq \pi( \beta)} \hat A'_\alpha p(\alpha,
 \beta) \right\vert
 & \leq &
\left(\sum_{\alpha \subseteq \pi( \beta)} \hat A'^2_\alpha\right)^{1/2}
\left(\sum_{\alpha \subseteq \pi( \beta)} p^2(\alpha, \beta)\right)^{1/2}
\nonumber \\
\leq \left(\sum_{\alpha \subseteq \pi( \beta)} p^2(\alpha, \beta)\right)^{1/2}
& \leq & (1-\epsilon )^{|\pi (\beta)|/2} \label{eq palphabeta}\enspace.
\end{eqnarray}
To see the last inequality in \eqref{eq palphabeta} note that
the sum equals
\begin{eqnarray}\label{eq palphabetamult}
\prod_{x \in  \pi (\beta)}
\left( \left(\frac 12 (1-(2\epsilon-1)^{s_x})\right)^2+
\left(\frac 12 (1+(2\epsilon-1)^{s_x})\right)^2\right)\enspace.
\end{eqnarray}
The factor corresponding to $x$ in \eqref{eq palphabetamult}
is of the form $a^2+b^2$
where $|a|+|b|=1$ and $\max (|a|,|b|) \leq 1-\epsilon$,
and hence it is bounded by $(1-\epsilon)$ and this gives the bound.

Our redesigned two-prover protocol enables us to control the
size of projections nicely.
\begin{lemma}\label{lem:no collison}
For any fixed $W$ and $\beta$ we have
\begin{eqnarray}\label{eq no}
{\rm Pr}_U [|\pi (\beta)| < |\beta |] < \frac {|\beta |^2}{2T}\enspace.
\end{eqnarray}
\end{lemma}

\begin{proof}
For the event in \eqref{eq no} to happen there must be
two different elements of $\beta$ that project to the same element.
There are at most $|\beta |^2/2$ pairs and the probability that any
pair project to the same element is at most $1/T$.  This follows
since two different elements differ in at least one
coordinate and the probability that a given coordinate does
not appear in $U$ is bounded above by $1/T$.  The lemma
follows from the union bound.
\end{proof}

Let us return to \eqref{eq abcfinal} and consider the
terms corresponding to a fixed $\beta$.
If $|\beta | \geq 2\epsilon^{-2}$ then  
using \lemref{lem:no collison},
we see, as $T\geq \epsilon^{-5}$,
that except with probability $2\epsilon$ we have
$| \pi (\beta )| \geq 2\epsilon^{-2}$ in which case
\eqref{eq palphabeta} is bounded by
$$
(1-\epsilon)^{\epsilon^{-2}} \leq e^{\epsilon^{-1}} \leq \epsilon\enspace.
$$
We conclude that
\begin{eqnarray} \label{eq abcsmall}
E_{U,W} \left[\sum_{|\beta| \geq 2\epsilon^{-2}, \alpha \subseteq \pi(\beta)}
 \hat A'_\alpha \hat B_\beta
\hat C_\beta p(\alpha, \beta)\right] \leq
E_{U,W} \left[\sum_{|\beta| \geq 2\epsilon^{-2}}
\hat B_\beta
\hat C_\beta (Pr[|\pi(\beta)| \leq 2\epsilon^{-1}]+ \epsilon)\right]
 \leq 3\epsilon.
\end{eqnarray}

It follows that
\begin{eqnarray} \label{eq abcfinal2}
E_{U,W} \left[\sum_{|\beta| \leq 2\epsilon^{-2}, \alpha \subseteq \pi(\beta)}
 \hat A'_\alpha \hat B_\beta
\hat C_\beta p(\alpha, \beta)\right] \geq \delta - 3\epsilon\enspace,
\end{eqnarray}
and we want to bound the contribution from
$\alpha=\emptyset$.  Note that if $|\beta | \leq 
2\epsilon^{-2}$ then, by \lemref{lem:no collison}, except
with probability $2\epsilon$ each $s_x$ is one.  In 
this case 
$$
p(\emptyset , \beta )= \epsilon^{|\beta|} \leq \epsilon
$$
and we conclude that the total expectation of terms containing
$\alpha=\emptyset$ is at most $3\epsilon$ and hence we have
\begin{eqnarray} \label{eq abcfinal3}
E_{U,W} \left[\sum_{|\beta| \leq 2\epsilon^{-2}, \emptyset\not= \alpha \subseteq \pi(\beta)}
 \hat A'_\alpha \hat B_\beta
\hat C_\beta p(\alpha, \beta)\right] \geq \delta - 6\epsilon\enspace.
\end{eqnarray}

Returning to \eqref{eq ss2} we see that the provers are successful
with with probability at least
$$
\frac {\epsilon^2} {2} E_{U,W} \left[ 
\sum_{\beta, \emptyset\not=\alpha \subseteq \pi( \beta),
|\beta | \leq 2 \epsilon^{-2} }
\hat A'^2_\alpha  \hat B_\beta^2 \right]\enspace.
$$
Now by the above reasoning we have the following chain of
equalities, where all sums are over the set
$$
\{ \beta, \emptyset\not= \alpha \subseteq \pi( \beta),|\beta| \leq
2\epsilon^{-2}\}\enspace:
$$


\begin{eqnarray*}
(\delta-6\epsilon)^2 \leq \left(
E_{U,W} \left[ \sum
\hat A'_\alpha  \hat B_\beta \hat C_\beta
p(\alpha, \beta) \right] \right)^2 & \leq  &
E_{U,W} \left[ \left(
\sum
\hat A'_\alpha \hat B_\beta \hat C_\beta
p(\alpha, \beta) \right)^2 \right] \leq \\
E_{U,W} \left[
\left( \sum
 \hat A'^2_\alpha \hat B_\beta^2\right)
\left(
\sum
 \hat C_\beta^2
p^2(\alpha, \beta) \right) \right] & \leq &
E_{U,W} \left[
\sum \hat A_\alpha'^2 \hat B_\beta^2 \right]\enspace,
\end{eqnarray*}
where the last inequality follows from
$$
\sum_\beta \sum_{\alpha \subseteq \beta} \hat C^2_\beta p^2(\alpha, \beta)
\leq
\sum_\beta \hat C^2_\beta \leq 1\enspace,
$$
where we again used the last inequality of \eqref{eq palphabeta}.
We conclude that the verifier in the two-prover protocol accepts
with the given strategies with probability at least
$\epsilon^2(\delta-6\epsilon)^2/2$ and the proof is complete.
\end{proof}

\section{The case of larger domains}\label{sec:mod p}

In this section we prove \thmref{thm:modp}.
This is done by a natural extension of the
protocols from the previous sections.
Before we present our protocols we give some
definitions and recall some background results.

\subsection{Background in the large domain case}

Let $\Z_p$ denote the multiplicative group given by the $p^{th}$ roots
of unity.  Let $\zeta = e^{2\pi i/p}$ be the basic $p^{th}$ root of unity.
To generalize the Boolean $\land$ we define an operation $\mult(\ , \ )$
as:
$$
\mult(\zeta^i, \zeta^j) = \zeta^{ij}\enspace.
$$
We have the following useful lemma
\begin{lemma}\label{lem:mult}
If $x$ and $y$ are $p^{th}$ roots of unity, we have      
$$
\mult(x,y)= \frac {1}{p} \sum_{i=0}^{p-1} \sum_{j=0}^{p-1} 
   x^i y^j \zeta^{-ij}\enspace.
$$
\end{lemma}

\begin{proof}
Suppose $y=\zeta^{i_0}$.  Fix $i$ and consider the inner sum.
For $i \not= i_0$ the value is 0 while for $i=i_0$ it
is $p$.  This implies that the total sum equals $x^{i_0}$
which is in fact $\mult(x,y)$.
\end{proof}

We define long $p$ codes as the natural extension
of the long code.  Positions
are indexed by functions $f: \{ -1,1\}^t \to \Z_p$
and in the code for $x$ this position takes value
$f(x)$.

Let $A$ be a table containing a value $A(f) \in \Z_p$
for every function $f: \{ -1,1\}^t \to \Z_p$.  We
make the following definitions for such a table.

\begin{definition} A table $A$ is folded over true if $A(\zeta^a f) = 
\zeta^a A(f)$, for  $ 0\leq a\leq p-1$ and all $f$. 
\end{definition} 

\begin{definition} A table  $A$ respects exponentiation if $A(f^a) 
= A(f)^a$ for $0 \leq a \leq p-1$ and all $f$. 
\end{definition} 

\begin{definition} A table $A$ is conditioned upon a function 
$h : \{-1,1\}^t \to \{1,\zeta\}$ (1 represents false and 
$\zeta$ represents true), if  $A(f)= A( \mult(f,h))$ for all $f$. 
\end{definition} 

Now we briefly explain Fourier analysis of long $p$-codes. For every 
function $\alpha : \{-1,1\}^t \to GF(p) $, where
$GF(p)$ is represented by $\{ 0, 1, \ldots p-1\}$, there is a  
character $\chi_\alpha$ defined as 
$$
\chi_\alpha(f) =  \prod_{x \in \{-1,1\}^t }  f(x)^{\alpha(x)}\enspace.
$$
Note that $\alpha$ is a ``function'' rather than a ``set'' as in binary
case and that the transform takes complex values.  We denote by $N(\alpha)$
the set on which $\alpha$ takes nonzero values i.\,e.,
$$
N(\alpha) = \{  x | \alpha(x) \not = 0 \}\enspace.
$$
Every table $A$ can be written as 
$A(f)  = \sum_{\alpha} \hat A_\alpha \chi_\alpha (f)$ with 
$\sum_\alpha |\hat A_\alpha|^2 = 1$.  
We can assume that tables are folded or conditioned upon a
given function by using appropriate access mechanisms.    
Following are easy consequences of folding and conditioning. 

\begin{lemma} \label{lem:p folding} If $A$ is folded over true and 
$\hat A_\alpha \not= 0$, then $\sum_{x \in \{-1,1\}^t} \alpha(x) = 
 1 \ \bmod p $.  In particular $N(\alpha)$ is a nonempty set.  
\end{lemma} 

%\begin{lemma} \label{lem:respect exp}  If $A$ respects exponentiation, 
%then all its Fourier coefficients $\hat A_\alpha$ are real numbers.
%\end{lemma} 

\begin{lemma} \label{lem:p conditioning} If $A$ is conditioned 
upon a function $h : \{-1,1\}^t \to \{1,\zeta\}$ and $\hat 
 A_\alpha \not = 0$, then for every $x \in N(\alpha)$, 
$h(x)$ is true, i.\,e., $h(x)= \zeta$. 
\end{lemma} 

In this section our numbers are elements of the number
field $\Q (\zeta)$,
the rational numbers with the $p^{th}$ root of unity added.
We use the homomorphism $\sigma_a$, $0\leq a \leq p-1$ which
has the property that $\sigma_a(\zeta^ i)= \zeta^{ia}$.
For $x$ a $p^{th}$ root of unity we have $\sigma_a(x)=x^a$
but this is not true in general.

We have the following straightforward lemma of which
we omit the proof.
\begin{lemma}\label{lem:pth root}
For $x\not= 1$ a $p^{th}$ root of unity we have
$$
\sum_{a=0}^{p-1} \sigma_a (x) =0\enspace.
$$
\end{lemma}

Finally define
$$
\pi_p(\beta)(x)= \sum_{y \in \pi^{-1}(x)} \beta(y) \bmod p
$$
as the generalization of $\pi_2$.  \lemref{lem:projection}
generalizes.

\begin{lemma}\label{lem:projectionp}
Let $\beta \subseteq \{-1,1\}^W$, $U \subseteq W$
and $f : \{-1, 1\}^ U \to \Z_p$.  Then
$$
\chi_{\beta} (f) = \chi_{\pi_p(\beta)} (f)\enspace.
$$
\end{lemma}


\subsection{The basic test}

We first define the basic test which is completely analogous to
the binary case. We assume that tables $A,B$ are folded over 
true and respect exponentiation. The table $B$ (supposed long 
$p$-code on $W$) is conditioned upon the CNF  formula $\varphi_W$. 

\medskip
\noindent
\textbf {Basic mod-{\em p}\, PCP}            

\begin{enumerate}

\item $V$ chooses $U$, $W$ and $\varphi_W$ as in
2PP$(u)$.

\item $V$ chooses two functions $f$ and $f'$ 
on $U$, taking values in $\Z_p$ uniformly at random.

\item $V$ chooses two random functions $g$ and $g'$ on
$W$ taking values in $\Z_p$ uniformly at random.  $V$
defines a third function $h$ by setting for each
$y \in \{ -1,1\}^W$, $h(y)=g(y)f(\pi(y))
 \ \mult(g'(y),f'(\pi (y)))$.

\item $V$ accepts iff $B(h)=B(g)A(f) \ \mult(B(g'),A(f'))$.

\end{enumerate}

Obviously the completeness of the basic test is 1
and we turn to the soundness.

\begin{lemma} If the verifier in the basic test accepts
with probability $(1+\delta)/p$ then there exists
a strategy for $P_1$ and $P_2$ in 2PP$(u)$
that makes the verifier accept with probability
$p^{-O(1)}\delta^{O(1)}$.
\end{lemma}

First note that 
$$
B(h)^{-1}B(g)A(f) \ \mult(B(g'),A(f'))
$$
is a $p^{th}$ root of unity which is 1 iff the test
accepts.

This implies,
under the hypothesis of the lemma and using
\lemref{lem:pth root}, that 
$$
E_{U,W,f,f',g,g'} [\sum_{a=1}^{p-1} 
\sigma_a (B(h)^{-1}B(g)A(f) \ \mult(B(g'),A(f')))] = \delta\enspace.
$$
Using \lemref{lem:mult} and the fact that our
tables respect exponentiation we see
that 
$$
E_{U,W,f,f',g,g'} [\sum_{b=0}^{p-1}\sum_{c=0}^{p-1}\sum_{a=1}^{p-1} 
B(h)^{-a}B(g^a)A(f^a) B(g'^{ab})A(f'^{ac})\zeta^{-bc}] =
p\delta\enspace.
$$
We conclude that there must be some value of $(a,b,c)$ such that
\begin{eqnarray}\label{eq basic mod p}
|E_{U,W,f,f',g,g'} [B(h)^{-a}B(g^a)A(f^a) B(g'^{ab}),A(f'^{ac})]| \geq
p^{-2}\delta\enspace.
\end{eqnarray}
Replacing $(h,g,f,g',f')$ by $(h^a, g^a, f^a,g'^a, f'^)$ preserves
probability and hence changing the value of $c$,
we can without loss of generality assume that $a=1$.

Fix $U,W, f'$ and $g'$ and let us study
\begin{eqnarray}\label{eq efg}
E_{f,g} [B(h^{-1})B(g)A(f)]\enspace.
\end{eqnarray}
Replacing each function by its Fourier expansion we see that
this equals
$$
\sum_{\beta_1,\beta_2,\alpha}\hat B_{\beta_1} \hat B_{\beta_2}
\hat A_\alpha E_{f,g} [\chi_{\beta_1} (f^{-1}g^{-1}\mult(f',g')^{-1})
\chi_{\beta_2} (g) \chi_{\alpha} (f)]\enspace.
$$
The inner expected value
is 0 unless $\beta_1=\beta_2$ and $\pi_p(\beta_1)=\alpha$ and
hence \eqref{eq efg} equals
\begin{eqnarray} 
\sum_\beta \hat B_\beta^2 \hat A_{\pi_p(\beta)} \chi_\beta (\mult(f',g')^{-1})\enspace.
\end{eqnarray}
Returning to \eqref{eq basic mod p} we need to analyze
\begin{eqnarray}\label{eq ef'g'}
E_{f',g'}[\chi_\beta (\mult(f',g')^{-1})B(g'^b) A(f'^c)]\enspace.
\end{eqnarray}
Fix the value of $f'$.  
When $b=0$, averaging over $g'$ gives $0$ unless  
$f'(\pi(z))=1$ for all $z \in N(\beta)$. The probability of picking 
such an $f'$ 
is $p^{-|\pi(N(\beta))|}$. Now consider the case when $b\not = 0$.  
Define $\beta'$ as follows: for every $y$,  
$\beta'(y) = b^{-1} e(y) \beta(y)$ where  $f'(\pi(y))=\zeta^{e(y)}$. 
Averaging \eqref{eq ef'g'} over $g'$ yields
$\hat B_{\beta'}
A(f'^c)$. 

We note that $f's$ which are different on  $\pi(N(\beta))$ 
give different $\beta'$. Let $\Delta_\beta$ be the set of all 
possible $\beta'$. We have $|\Delta_\beta|=p^{|\pi(N(\beta))|} $
 and over all the choices of $f'$, every   
$\beta' \in \Delta_\beta$ occurs equally often. 
Using this observation and applying the Cauchy-Schwarz inequality  
gives
\begin{eqnarray*}
| \ E_{f'} [ \hat B_{\beta'} A(f'^c)] \ | \ \leq \ 
E_{f'}[|\hat B_{\beta'}|] & =  & p^{-|\pi(N(\beta))|} 
\sum_{ \beta' \in \Delta_\beta } |\hat B_{\beta'}|  \ \leq \\
p^{- |\pi(N(\beta))|/2} \left( \sum_{ \beta' \in \Delta_\beta} |\hat B_{\beta'}|^2
\right)^{1/2} & \leq & p^{-|\pi(N(\beta))|/2}\enspace.
\end{eqnarray*}


This implies that we get an overall upper bound on  
the expectation of \eqref{eq basic mod p}  as 
$$ 
E_{U,W} \left[ \sum_\beta |\hat B_\beta|^2  \  |\hat A_{\pi_p(\beta)}| 
 \ p^{- |\pi(N(\beta))|/2} \right]\enspace.
$$
Now we can extract prover strategies in a similar way  as in the proof 
of \lemref{lem:basic test}, making use of \eqref{eq size pi}. A 
minor difference is that now $\alpha$ ( $\beta$ )  are functions and not 
sets. The provers pick $\alpha$ ( $\beta$ ) with probability $\hat
A_\alpha^2 $ ( $\hat B_\beta^2$ ) and  pick a random $x \in N(\alpha)$ 
 (a random $y \in N(\beta)$ ). 
 

\subsubsection{Iterated tests}
The basic test in the previous section can be iterated in  
a way similar to the \secref{sec:iterated  binary}.  
We have only attempted the simpler
analysis of almost disjoint sets and this is what we
present here.  

\subsubsection{The almost disjoint sets test}

We first define the test which is an iteration
of the basic test studied in the last section.


\medskip
\noindent
\textbf{{\em k}-iterated mod-{\em  p}\, almost disjoint sets PCP}

\begin{enumerate}

\item $V$ chooses $U$ as in 2PP$(u)$.

\item $V$ chooses independently $k$ sets $(W_l)_{l=1}^k$,
that can appear with $U$ in 2PP$(u)$.  Each $W_l$ is chosen
with the distribution induced by 2PP$(u)$, i.\,e., the
distribution of the pair $U,W_l$ is the same as the
distribution of $U,W$ in 2PP$(u)$.

\item $V$ chooses $2k$ functions $(f_i)_{i=1}^k$ and $(f'_j)_{j=1}^k$ 
on $U$ taking values in $\Z_p$ uniformly at random.

\item For each $l$, $1\leq l\leq k$,
 $V$ chooses two functions $g_l$ and $g'_l$ on
$W_l$ taking values in $\Z_p$ uniformly at random.

\item For each triple $i,j,l$ such that $i+j+l\equiv 0 \bmod k$
 define a function $h_{ijl}$ by setting for each
$y \in \{ -1,1\}^{W_l}$, $h_{ijl}(y)=g_l(y)f_i(\pi(y))
\mult(g'_l(y),f'_j(\pi (y)))$.

\item $V$ accepts iff $B_{W_l}(h_{ijl})=B_{W_l}(g_l)A_U(f_i) 
\mult(B_{W_l}(g'_l), A_U(f'_j))$ for all $i+j+l\equiv 0 \bmod k$.

\end{enumerate}

We have the following theorem.
\begin{theorem}\label{thm:almost disjoint p}
The almost disjoint sets test in $\Z_p$ has completeness $1$ and
soundness $p^{-k^2}+p^{O(1)}d_c^{\Omega (u)}$, where $d_c$ is
the constant from \thmref{thm:2ppu}.
\end{theorem}

\begin{proof}
The completeness is obvious and we need to analyze the soundness.
To this end let
$$
\Acc(i,j,l)=B_l(h_{ijl})^{-1} B_l(g_l) A(f_i) \ \mult(A(f_j'),B_l(g_l'))\enspace,
$$
which is 1 if the test associated with $(i,j,l)$ accepts and
otherwise it is a different $p^{th}$ root of unity.

Let $Z_0$ be the set of all triples $(i,j,l)$ with $i+j+l \equiv 
 0 (\mbox{\ mod \ k})$ and 
let $S \in GF(p)^{k^2}$ be a vector whose coordinates are indexed 
by the triples  in $Z_0$.  We have
$$
\prod_{(i,j,l) \in Z_0} \frac {\sum_{a=0}^{p-1}
 (\Acc(i,j,l))^a}{p}  =
p^{-k^2} \sum_{S \in GF(p)^{k^2} } \prod_{(i,j,l)\in Z_0 }
 (\Acc(i,j,l))^{S(i,j,l)}\enspace.
$$
By \lemref{lem:pth root} this expression  equals $1$ if the test
 accepts and is $0$ otherwise
and thus its expected value is the probability that the test
accepts.  The term with $S \equiv 0$ is 1 and to establish
the theorem it is sufficient to establish that any
term with $S \not\equiv 0$ is upper bounded above by 
$p^{O(1)}d_c^{\Omega (u)}$.  Let $T_S$ be
the expected value of the term corresponding to $S$.
We go on to establish a strategy for $P_1$ and $P_2$ which
makes the verifier in 2PP$(u)$ accept with probability
$p^{-O(1)}|T_S|^{O(1)}$.

Suppose without loss of generality that $S(k,k,k)=r \not=0$
and fix
the values of $f_i$, $i\not= k$, $f_j$, $j\not= k$
and $(W_l, g_l, g_l')$ for $l\not= k$ in such a way
as not to decrease $|T_S|$.
Since we only have one remaining function of each type
let us for readability discard the index.

By \lemref{lem:mult}
and from the fact that any other triple intersects 
with the given triple in at most one place we conclude
that $T_S$, after the above
fixings, can be written as the sum  of $p^2$ terms of  
the form
\begin{eqnarray}\label{eq type bac}
B(h)^{-r}A'(f)A''(f')C(g,g')\enspace,
\end{eqnarray}
each with a coefficient of complex absolute value
$1/p$.  Here $A'$, $A''$, $B$,  and $C$ takes values which
are $p^{th}$ roots of unity.  We conclude that there
is such an expression of the form \eqref{eq type bac} 
whose expectation over
$U, W, h, f, f', g ,$ and  $g'$ is at least $|T_S|/p$.


Here $A'$ and $A''$ are functions that only depend on $U$ and
hence might be used to extract
strategy for $P_2$. $B$ is the original long $p$-code on $W=W_{k}$
and hence is useful for extracting strategy for $P_1$.

We now want to compute the expected value of this expression
over random choices of $f$, $f'$, $g$ and $g'$.
Expanding all factors except $A''(f')$ by the Fourier transform we get
\begin{eqnarray}\label{eq abc1 p}
\sum_{\alpha, \beta,\gamma, \gamma'} \hat A'_\alpha
\hat B_{\beta} \hat C_{\gamma, \gamma'} 
E[\chi_\alpha (f) \chi_{-r\beta} (g f \ \mult(f',g')) 
\chi_{\gamma}(g)\chi_{\gamma'}(g')A''(f')]\enspace.
\end{eqnarray}
Now taking the expected value over $f$ we see that unless
$\alpha = r \pi_p(\beta)$ the term is 0.  Similarly we need
$\gamma = r\beta$. 
Fix $f'$ and define $\beta'$ as follows: for every $y$, 
$\beta'(y) = r e(y) \beta(y)$ where $f'(\pi(y))= \zeta^{e(y)}$. 
With this definition, we have 
$$
\chi_{-r \beta}(\mult(f',g')) = \chi_{-\beta'}(g')\enspace.
$$ 
Thus unless $\gamma'=\beta'$, the expectation is $0$. Thus
\eqref{eq abc1 p} equals
\begin{equation} \label{eq abc p}
  \sum_{\beta}  \hat {A'}_{r \pi_p(\beta)} \hat B_\beta 
 \hat C_{\beta, \beta'} A''(f')  \enspace.
\end{equation} 
Note that $\beta'$ is uniquely determined by $\beta$ 
and $f'$ and functions $f'$ 
which are different on $\pi(N(\beta))$ give different $\beta'$s.  
Let $\Delta_\beta$ be the set of all possible $\beta'$s. 
We have $|\Delta_\beta|=p^{|\pi(N(\beta))|} $
 and over all the choices of $f'$, every   
$\beta' \in \Delta_\beta$ occurs equally often. 
This implies that  
\begin{eqnarray}
| \ E_{f'}[ \hat C_{\beta, \beta'(\beta,f')} A''(f')] \ | \ 
 &\leq & E_{f'}[|\hat C_{\beta , \beta'(\beta,f')}|]  \ \leq  \\ \nonumber
p^{-|\pi(N(\beta))|} \sum_{\beta'\in \Delta_\beta}
|\hat C_{\beta , \beta'}|  \ & \leq & \ 
p^{-|\pi(N(\beta))|/2} (\sum_{\beta'\in \Delta_\beta}
|\hat C_{\beta , \beta'}|^2)^{1/2}\enspace.
\end{eqnarray}
Substituting this estimate into \eqref{eq abc p} and using the
Cauchy-Schwarz inequality                           
over $\beta$ we get the upper estimate
\begin{eqnarray*}
\left( \sum_\beta |\hat B_\beta|^2 |\hat A'_{r\pi_p(\beta)}|^2
p^{-|\pi(N(\beta))|} \right)^{1/2}
\left( \sum_{\beta,\beta'\in \Delta_\beta} |\hat C_{\beta,\beta'}|^2 \right)^{1/2}
\leq 
\left( \sum_\beta |\hat B_\beta|^2 |\hat A'_{r\pi_p(\beta)}|^2
p^{-|\pi (N(\beta))|} \right)^{1/2}
\end{eqnarray*}
for $|T_S|/p$.  The same strategy as defined in the basic
test now makes the verifier accept  in 2PP$(u)$ with
probability $p^{-O(1)}|T_S|^{O(1)}$ and the theorem follows.
\end{proof}

\section{Conclusions}\label{sec:conclusion}

We have established that the query efficient test of Samorodnitsky
and Trevisan can be extended to include perfect completeness
in several different ways.  The tests are simple and
the analyses are only moderately complicated, in particular
the proofs using the approach of \cite{hw} are fairly
straightforward.

All this taken together gives us good hope that, in the
not too distant future, we will see more powerful PCPs with
even more applications to inapproximability of NP-hard
optimization problems.  In particular the fact that we
can include perfect completeness gives hope that stronger
lower bounds for coloring of graphs of small chromatic
number could be possible.  Clearly, to obtain such results,
obstacles of other nature need also be overcome.
We note that some progress for constant colorable
graphs has already occurred \cite{kh}, but getting
strong results for 3-colorable graphs seems to require
new ideas.

\section{Acknowledgments} 
We  would like to thank  Sanjeev Arora for 
several helpful discussions. We are also grateful
to the anonymous referees for many comments that helped
to improve the quality of the paper.

\bibliography{a007}

\begin{tocauthors}
\begin{tocinfo}[johan]
  Johan H{\aa}stad \\
  professor \\
  Royal Institute of Technology, Stockholm, Sweden \\
  johanh\tocat{}nada\tocdot{}kth\tocdot{}se \\
  \url{http://www.nada.kth.se/~johanh}
\end{tocinfo}
\begin{tocinfo}[subhash]
  Subhash Khot \\
  assistant professor \\
  Georgia Instiute of Technology, Atlanta GA 30332 \\
  khot\tocat{}cc\tocdot{}gatech\tocdot{}edu \\
  \url{http://www.cc.gatech.edu/~khot}
\end{tocinfo}
\end{tocauthors}

\begin{tocaboutauthors}
\begin{tocabout}[johan]
{\sc Johan H{\aa}stad} graduated from M.I.T.  in 1986.  His advisor
was \href{http://theory.lcs.mit.edu/~shafi}{Shafi Goldwasser}.
He won the \href{http://sigact.acm.org/prizes/godel/1994.html}
{1994 G\"odel Prize} for his work on circuit complexity.  He is
a member of the Royal Academy of Sciences (Sweden) and was an
invited speaker at ICM 1998 and a plenary speaker at ECM 2004.
His CS interests include cryptography, complexity theory and 
approximability of NP-hard optimization problems.  He also enjoys 
table tennis and wine.
\end{tocabout}
\begin{tocabout}[subhash]
{\sc Subhash Khot} graduated from Princeton University in 2003
under the supervision of Prof. 
\href{http://www.cs.princeton.edu/~arora}{Sanjeev Arora}.   He won the Best 
Student Paper award at FOCS 2003 and shared the Best Paper Award 
at FOCS 2004.  He is interested in complexity theory, approximability 
of NP-hard problems and the theory of metric embeddings. He loves 
watching movies, cooking, and hanging out with friends and the family. 
Once an avid fan of cricket, he is not interested in the game anymore, 
thanks to the dismal performance of the Indian cricket team over the 
past several years.
\end{tocabout}
\end{tocaboutauthors}

\end{document}
