TR98-066 Authors: Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra

Publication: 26th November 1998 09:28

Downloads: 962

Keywords:

This paper strengthens the low-error PCP characterization of NP, coming

closer to the ultimate BGLR conjecture. Namely, we prove that witnesses for

membership in any NP language can be verified with a constant

number of accesses, and with an error probability exponentially

small in the number of bits accessed, as long as this number is

at most $(\log n)^{\beta}$ for {\em any} constant $\beta <

1$. (Compare with the BGLR conjecture, claiming the same for

any $\beta\le 1$).

Our results are in fact stronger, implying that the

constant-depend Gap-Quadratic-Solvability problem with field-size

$2^{\log^{\beta}n}$ is NP-hard. We show that given a

system of quadratic polynomials each depending on a constant

number of variables ranging over a field $\fld$ ($\card\fld

\approx 2^{\log^\beta n}$ for any constant $\beta<1$), it is NP-hard

to decide between the case where there is a common root for all of the

polynomials, and the case where every assignment zeros at most an

$O(\frac{1}{\card\fld})$ fraction.

At the same time, our proof presents a {\em direct}

construction of a low-degree-test whose error-probability is

exponentially small in the number of bits accessed. Such a

result was previously known only by relying on recursive

applications of the PCP theorem.