Access Restriction

Author Ben-Sasson, Eli ♦ Kaplan, Yohay ♦ Kopparty, Swastik ♦ Meir, Or ♦ Stichtenoth, Henning
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2016
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword PCPs ♦ Algebraic-geometric codes ♦ Error-correcting codes ♦ Probabilistic proof systems ♦ Sublinear time algorithms
Abstract The PCP theorem [Arora et al. 1998; Arora and Safra 1998] 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, that is, how long is the PCP compared to the original NP-proof? The state-of-the-art work of Ben-Sasson and Sudan [2008] and Dinur [2007] shows that one can encode proofs of length $\textit{n}$ by PCPs of length $\textit{n}$ · poly log $\textit{n}$ that can be verified using a constant number of queries. In this work, we show that if the query complexity is relaxed to $n^{ϵ},$ then one can construct PCPs of length $\textit{O}(\textit{n})$ for circuit-SAT, and PCPs of length $\textit{O}(\textit{t}log$ $\textit{t})$ for any language in $NTIME(\textit{t}).$ More specifically, for any ϵ > 0, we present (nonuniform) probabilistically checkable proofs (PCPs) of length $2^{O(1/ϵ)}$ · $\textit{n}$ that can be checked using $n^{ϵ}$ queries for circuit-SAT instances of size $\textit{n}.$ Our PCPs have perfect completeness and constant soundness. This is the first constant-rate PCP construction that achieves constant soundness with nontrivial query complexity $(\textit{o}(\textit{n})).$ 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 that are crucial in earlier high-rate 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 in the appendix to this article for the first time for every message length, building on an earlier construction for infinitely many message lengths by Stichtenoth [2006].
Description Author Affiliation: Haifa University, Haifa, Israel (Meir, Or); Rutgers, Brunswick, NJ (Kopparty, Swastik); Technion, Haifa, Israel (Ben-Sasson, Eli; Kaplan, Yohay); Sabanci University, Istanbul, Turkey (Stichtenoth, Henning)
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2016-11-08
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 63
Issue Number 4
Page Count 57
Starting Page 1
Ending Page 57

Open content in new tab

   Open content in new tab
Source: ACM Digital Library