Two-query PCP with subconstant error

Dana Moshkovitz, Ran Raz

Research output: Contribution to journalArticle

63 Scopus citations

Abstract

We show that the NP-Complete language 3SAT has a PCP verifier that makes two queries to a proof of almost-linear size and achieves subconstant probability of error ε = o(1). The verifier performs only projection tests, meaning that the answer to the first query determines at most one accepting answer to the second query. The number of bits representing a symbol in the proof depends only on the error ε. Previously, by the parallel repetition theorem, there were PCP Theorems with two-query projection tests, but only (arbitrarily small) constant error and polynomial size. There were also PCP Theorems with subconstant error and almost-linear size, but a constant number of queries that is larger than 2.

Original languageEnglish (US)
Article number29
JournalJournal of the ACM
Volume57
Issue number5
DOIs
StatePublished - Jun 1 2010
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Keywords

  • Composition
  • Label cover
  • Locally decode/reject code (LDRC)
  • Probabilistically checkable proofs (PCP)

Fingerprint Dive into the research topics of 'Two-query PCP with subconstant error'. Together they form a unique fingerprint.

  • Cite this