Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR98-066 | 3rd November 1998 00:00

PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability


Authors: Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra
Publication: 26th November 1998 09:28
Downloads: 1110


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.

ISSN 1433-8092 | Imprint