The error probability of Probabilistically Checkable Proof (PCP)
systems can be made exponentially small in the number of queries
by using sequential repetition. In this paper we are interested
in determining the precise rate at which the error goes down in
an optimal protocol, and we make substantial progress toward a
tight resolution of this question.

A PCP verifier uses q amortized query bits if, for some t, it
makes qt queries and has error probability at most 2^{-t}. A PCP
characterization of NP using 2.5 amortized query bits is known
[Trevisan, 1998a], and, unless P=NP, no such characterization is
possible using 1 amortized query bits [Bellare et al., 1998]. We
present a PCP characterization of NP that uses roughly 1.5
amortized query bits. Our result has two main implications.

Separating PCP from 2-Provers 1-Round:
In the 2-Provers 1-Round (2P1R) model the verifier has access to
two oracles (or provers) and can make one query to each oracle.
Each answer is a string of l bits (l is called the answer size).
A 2P1R protocol with answer size l can be simulated by a PCP
that reads 2l bits; we show that the converse does not hold for
l >= 7, unless P=NP. No such separation was known before.

The Max k-CSP problem:
The Boolean constraint satisfaction problem with constraints
involving at most k variables, usually called Max k-CSP, is known
to be hard to approximate within a factor 2^{-.4k} [Trevisan,
1998a], and a 2^{1-k}-approximation algorithm is also known
[Trevisan, 1998b]. We prove that Max k-CSP is NP-hard to
approximate within a factor of roughly 2^{-2k/3}.