Two query PCP with sub-constant error

Dana Moshkovitz, Ran Raz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

20 Scopus citations

Abstract

We show that the NP-Complete language 3SAT has a PCP verifier that makes two queries to a proof of almostlinear size and achieves sub-constant 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. Previously, by the parallel repetition theorem, there were PCP Theorems with two-query projection tests, but only (arbitrarily small) constant error and polynomial size [26]. There were also PCP Theorems with sub-constant error and almost-linear size, but a constant number of queries that is larger than 2 [22]. As a corollary, we obtain a host of new results. In particular, our theorem improves many of the hardness of approximation results that are proved using the parallel repetition theorem. A partial list includes the following: 1. 3SAT cannot be efficiently approximated to within a factor of 7/8 + o(1), unless V = NP. This holds even under almost-linear reductions. Previously, the best known NP-hardness factor was 7/8 + ε for any constant ε > 0, under polynomial reductions (Håstad, [17]). 2. 3LIN cannot be efficiently approximated to within a factor of 1/2 + o(1), unless P = NP. This holds even under almost-linear reductions. Previously, the best known NP-hardness factor was 1/2 + ε for any constant ε > 0, under polynomial reductions (Håstad, [17]). 3. A PCP Theorem with amortized query complexity 1 + o(1) and amortized free bit complexity o(1). Previously, the best known amortized query complexity and free bit complexity were 1 + ε and ε, respectively, for any constant ε > 0 (Samorodnitsky and Trevisan, [29]). One of the new ideas that we use is a new technique for doing the composition step in the (classical) proof of the PCP Theorem, without increasing the number of queries to the proof. We formalize this as a composition of new objects that we call Locally Decode/Reject Codes (LDRC). The notion of LDRC was implicit in several previous works, and we make it explicit in this work. We believe that the formulation of LDRCs and their construction are of independent interest.

Original languageEnglish (US)
Title of host publicationProceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008
Pages314-323
Number of pages10
DOIs
StatePublished - Dec 30 2008
Externally publishedYes
Event49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008 - Philadelphia, PA, United States
Duration: Oct 25 2008Oct 28 2008

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008
CountryUnited States
CityPhiladelphia, PA
Period10/25/0810/28/08

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

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

  • Cite this

    Moshkovitz, D., & Raz, R. (2008). Two query PCP with sub-constant error. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008 (pp. 314-323). [4690965] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2008.60