Sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP

Ran Raz, Shmuel Safra

Research output: Contribution to journalConference articlepeer-review

553 Scopus citations

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 ε>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-ε)n. Our results are in fact stronger, as stated below. 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.

Original languageAmerican English
Pages (from-to)475-484
Number of pages10
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - 1997
Externally publishedYes
EventProceedings of the 1997 29th Annual ACM Symposium on Theory of Computing - El Paso, TX, USA
Duration: May 4 1997May 6 1997

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP'. Together they form a unique fingerprint.

Cite this