# DIMACS Princeton Theory Seminar

## Title:

Sub-Constant Error PCP Characterization of NP

## Speaker:

- Ran Raz
- Weizmann Institute

## Place:

- Room 402, Computer Science Building
- 35 Olden Street
- Princeton University.

## Time:

- 12:05 PM (Lunch will be served at 11:45 AM)
- Thursday, April 24, 1997 - Note change of day

## Contact:

- Sanjeev Arora (arora@cs.princeton.edu)

## Abstract:

We introduce a new low-degree--test, one that uses the restriction of
low-degree polynomials to planes (i.e., affine sub-spaces of dimension
2), rather than the restriction to lines (i.e., affine sub-spaces of
dimension 1). We prove the new test to be of a very small
error-probability (in particular, much smaller than constant).
The new test enables us to prove a low-error characterization
of NP in terms of PCP. Specifically, our theorem states that, for any
given $\epsilon > 0$, membership in any NP language can be verified
with $O(1)$ accesses, each reading logarithmic number of bits, and
such that the error-probability is $2^{-\log^{1 -\epsilon}n}$. Our
results are in fact stronger.

One application of the new characterization of NP is that
approximating SET-COVER to within a logarithmic factors is NP-hard.

Previous analysis for low-degree--tests, as well as previous
characterizations of NP in terms of PCP, have managed to
achieve, with constant number of accesses, error-probability of, at
best, a constant. The proof for the small error-probability of our new
low-degree--test is, nevertheless, significantly simpler than previous
proofs. In particular, it is combinatorial and geometrical in nature,
rather than algebraic.

Joint work with S. Safra (Tel-Aviv University)

Document last modified on April 11, 1997