Short PCPs verifiable in polylogarithmic time

By Eli Ben-Sasson, Oded Goldreich, P. Harsha, Madhu Sudan, Salil P. Vadhan. 2005

118 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Verifying Computations with Streaming Interactive Proofs (2011, unknown): “In [5], Ben-Sasson et al.”
Scalable, transparent, and post-quantum secure computational integrity (2018, methodology): “The ideas used in both reduction are based on ideas from [91, 25, 27, 19, 38] where affine graphs are used to encode and verify program traces.”
Efficient Arguments without Short PCPs (2007, background): “Note that in Step (1) above a classical proof is expanded by introducing a significant amount of redundancy, whereas in Step (2) it dramatically shrinks in size.”
Spartan: Efficient and general-purpose zkSNARKs without trusted setup (2020, background): “While many works on PCPs focus on proving inapproximability results [45], there is long line of work to reduce the length of a PCP, and to improve the asymptotic costs of proof generation and verification [17, 23, 25].”
Introduction to Property Testing (2017, unknown): “The interested reader is referred to [45, 205].”
Computational Integrity with a Public Random String from Quasi-Linear PCPs (2017, methodology): “Observing that (i) these PCPPs are built using recursive PCPP composition [BGH + 06], and (ii) only a small fraction of recursive branches are explored by the verifier, we increase the number of rounds of interaction and use a notarized interactive proof of proximity (NIPP) [BBGR16], a special case ”
Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture (2014, background): “Despite achieving essentially-optimal asymptotics [6, 18, 15, 14, 21] no implementations of them have been reported to date.”
Resolving the conflict between generality and plausibility in verified computation (2013, background): “Unfortunately, the naturally-implementable “textbook” PCPs [44] are too large to be transferred (and other PCPs, while asymptotically short [11, 12, 24], appear to have prohibitive constants).”
Scalable Zero Knowledge with No Trusted Setup (2019, background): “The early theoretical constructions that achieved the six properties above were based on the celebrated PCP Theorem [2, 3, 6, 5] and ZK variants of PCPs (ZK-PCPs) [39, 55, 52].”