PCP characterizations of NP: Towards a polynomially-small error-probability

Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra

Research output: Contribution to journalConference article

36 Scopus citations

Abstract

This paper strengthens the low-error PCP characterization of NP, coming closer to the upper limit of the 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, where this number is as high as logbeta n, for any constant β<1. (The BGLR conjecture claims the same for any β≤1). Our results are in fact stronger, implying the Gap-Quadratic-Solvability problem to be NP-hard even if the equations are restricted to having a constant number of variables. That is, given a system of quadratic-equations over a field F (of size up to 2log(β) n), where each equation depends on a constant number of variables, it is NP-hard to decide between the case where there is a common solution for all of the equations, and the case where any assignment satisfies no more than a 2/|F| fraction of them. At the same time, our proof presents a 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 relying on recursive applications of the entire PCP theorem.

Original languageEnglish (US)
Pages (from-to)29-40
Number of pages12
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - Jan 1 1999
Externally publishedYes
EventProceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 - Atlanta, GA, USA
Duration: May 1 1999May 4 1999

All Science Journal Classification (ASJC) codes

  • Software

Cite this