Constant rate PCPs for circuit-SAT with sublinear query complexity

Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth

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

8 Scopus citations

Abstract

The PCP theorem (Arora et. al., J. ACM 45(1,3)) says that every NP-proof can be encoded to another proof, namely, a probabilistically checkable proof (PCP), which can be tested by a verifier that queries only a small part of the PCP. A natural question is how large is the blow-up incurred by this encoding, i.e., how long is the PCP compared to the original NP-proof. The state-ofthe- Art work of Ben-Sasson and Sudan (SICOMP 38(2)) and Dinur (J. ACM 54(3)) shows that one can encode proofs of length n by PCPs of quasi-linear length that can be verified using a constant number of queries. In this work, we show that if the query complexity is relaxed to polynomial, then one can construct PCPs of linear length for circuit - SAT, and PCPs of length O(tlog t) for any language in NTIME(t). Our PCPs have perfect completeness and constant soundness. This is the first constant-rate PCP construction that achieves constant soundness with nontrivial query complexity. Our proof replaces the low-degree polynomials in algebraic PCP constructions with tensors of transitive algebraic geometry (AG) codes. We show that the automorphisms of an AG code can be used to simulate the role of affine transformations which are crucial in earlier highrate algebraic PCP constructions. Using this observation we conclude that any asymptotically good family of transitive AG codes over a constant-sized alphabet leads to a family of constant-rate PCPs with polynomially small query complexity. Such codes are constructed for the first time for every message length.

Original languageEnglish (US)
Title of host publicationProceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
Pages320-329
Number of pages10
DOIs
StatePublished - Dec 1 2013
Event2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 - Berkeley, CA, United States
Duration: Oct 27 2013Oct 29 2013

Publication series

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

Other

Other2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
CountryUnited States
CityBerkeley, CA
Period10/27/1310/29/13

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • AG codes
  • Computational complexity
  • Probabilistically checkable proofs

Cite this

Ben-Sasson, E., Kaplan, Y., Kopparty, S., Meir, O., & Stichtenoth, H. (2013). Constant rate PCPs for circuit-SAT with sublinear query complexity. In Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 (pp. 320-329). [6686168] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2013.42