TR98-040 Authors: Madhu Sudan, Luca Trevisan

Publication: 27th July 1998 09:37

Downloads: 1004

Keywords:

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}.