ECCC-Report TR98-066https://eccc.weizmann.ac.il/report/1998/066Comments and Revisions published for TR98-066en-usThu, 26 Nov 1998 09:28:10 +0200
Paper TR98-066
| PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability |
Irit Dinur,
Eldar Fischer,
Guy Kindler,
Ran Raz,
Shmuel Safra
https://eccc.weizmann.ac.il/report/1998/066 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.
Thu, 26 Nov 1998 09:28:10 +0200https://eccc.weizmann.ac.il/report/1998/066