Short PCPs with Polylog Query Complexity
The DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.
Abstract
We give constructions of probabilistically checkable proofs (PCPs) of length $n \cdot polylog n$ proving satisfiability of circuits of size n that can be verified by querying $polylog n$ bits of the proof. We also give analogous constructions of locally testable codes (LTCs) mapping n information bits to $n\cdot polylog n$ bit long codewords that are testable with $polylog n$ queries. Our constructions rely on new techniques revolving around properties of codes based on relatively high-degree polynomials in one variable, i.e., Reed–Solomon codes. In contrast, previous constructions of short PCPs, beginning with [L. Babai, L. Fortnow, L. Levin, and M. Szegedy, Checking computations in polylogarithmic time, in Proceedings of the 23rd ACM Symposium on Theory of Computing, ACM, New York, 1991, pp. 21–31] and until the recent [E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan, and S. Vadhan, Robust PCPs of proximity, shorter PCPs, and applications to coding, in Proceedings of the 36th ACM Symposium on Theory of Computing, ACM, New York, 2004, pp. 13–15], relied extensively on properties of low-degree polynomials in many variables. We show how to convert the problem of verifying the satisfaction of a circuit by a given assignment to the task of verifying that a given function is close to being a Reed–Solomon codeword, i.e., a univariate polynomial of specified degree. This reduction also gives an alternative to using the “sumcheck protocol” [C. Lund, L. Fortnow, H. Karloff, and N. Nisan, J. ACM, 39 (1992), pp. 859–868]. We then give a new PCP for the special task of proving that a function is close to being a Reed–Solomon codeword. The resulting PCPs are not only shorter than previous ones but also arguably simpler. In fact, our constructions are also more natural in that they yield locally testable codes first, which are then converted to PCPs. In contrast, most recent constructions go in the opposite direction of getting locally testable codes from PCPs.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The complexity of theorem-proving procedures
Cook, S. A. (1971) · Proceedings of the third annual ACM symposium on Theory of computing - STOC '71 · doi:10.1145/800157.805047 · Cited by 6,385
Some optimal inapproximability results
Håstad, J. (2001) · Journal of the ACM · doi:10.1145/502090.502098 · Cited by 1,902
Micali, S. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539795284959 · Cited by 424
Cited by
Hawk: The Blockchain Model of Cryptography and Privacy-Preserving Smart Contracts
Kosba, A., Miller, A., Shi, E., Wen, Z., & Papamanthou, C. (2016) · 2016 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2016.55 · Cited by 2,227
“Examples include recursively composed SNARKs [18], [25] or other efficient PCP constructions [16].”
BackgroundO'Donnell, R. (2014) · Cambridge University Press eBooks · doi:10.1017/cbo9781139814782 · Cited by 932
SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge
Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E., & Virza, M. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-40084-1_6 · Cited by 598
Self-citationBitansky, N., Canetti, R., Chiesa, A., & Tromer, E. (2012) · Proceedings of the 3rd Innovations in Theoretical Computer Science Conference · doi:10.1145/2090236.2090263 · Cited by 493
Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS
Chiesa, A., Hu, Y., Maller, M., Mishra, P., Vesely, N., & Ward, N. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-45721-1_26 · Cited by 358
Metadata
- Authors
- Ben-Sasson, E., & Sudan, M.
- Venue
- SIAM Journal on Computing
- Published
- 2008-01
- Volume
- 38
- Issue
- 2
- Pages
- 551-607
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2087900794
- Cited by
- 147
- References
- 3
- FWCI
- 9.58
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.