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

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

Research output: Contribution to journalArticle

10 Scopus citations

Abstract

This paper strengthens the low-error PCP characterization of NP, coming closer to the upper limit of the BGLR conjecture. Consider the task of verifying a written proof for the membership of a given input in an NP language. In this paper, this is achieved by making a constant number of accesses to the proof, obtaining error probability that is exponentially small in the total number of bits that are read. We show that the number of bits that are read in each access to the proof can be made as high as logβn, for any constant β < 1, where n is the length of the proof. The BGLR conjecture asserts the same for any constant β, for β smaller or equal to 1. Our results are in fact stronger, implying that the Gap-Quadratic-Solvability problem with a constant number of variables in each equation is NP-hard. That is, given a system of n 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 distinguish between the case where there is a common solution to all of the equations and the case where any assignment satisfies at most a 2/{divides}F{divides} 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)413-504
Number of pages92
JournalComputational Complexity
Volume20
Issue number3
DOIs
StatePublished - Sep 1 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Mathematics(all)
  • Computational Theory and Mathematics
  • Computational Mathematics

Keywords

  • NP
  • PCP
  • consistent-reader
  • low-degree extension
  • representation-procedure
  • sum-check

Fingerprint Dive into the research topics of 'PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability'. Together they form a unique fingerprint.

  • Cite this