The PCP theorem by gap amplification
By Irit Dinur. Symposium on the Theory of Computing, 2006
426 citations recorded by the source corpus.
Subfields: Artificial Intelligence, Computational Theory and Mathematics
View Paper: https://www.semanticscholar.org/paper/57d234d1fedbe72e7722b959b967a85ed4e78686
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
- Srinath T. V. Setty
- Michael Walfish
- Andrew Justin Blumberg
- Justin Thaler
- Yuval Ishai
- Eli Ben-Sasson
- Jens Groth
- Bryan Parno
In Computational Theory and Mathematics
- Srinath T. V. Setty
- Michael Walfish
- Andrew Justin Blumberg
- Justin Thaler
- Yuval Ishai
- Eli Ben-Sasson
- Jens Groth
- Bryan Parno
Citations in the corpus
- 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.”
- Infeasibility of instance compression and succinct PCPs for NP (2007, neutral): “Current proofs of the PCP theorem [3, 2, 9] do not yield such PCPs.”
- 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).”
- Introduction to Property Testing (2017, methodology): “, [94, 92]), and lower error via few multi-valued queries (e.”
- Taking Proof-Based Verified Computation a Few Steps Closer to Practicality (2012, methodology): “Applying proof systems to verifiable computation is standard in the theory community [5–7, 10, 16, 32, 37, 38, 43], and the asymptotics continue to improve [13, 14, 23, 46].”
- Sub-linear Zero-Knowledge Argument for Correctness of a Shuffle (2008, methodology): “This method, however, requires a reduction to Circuit Satisfiability, a subsequent application of the PCP-theorem [4, 3, 12], and using a collision-free hash-function to build a hash-tree that includes the entire PCP.”
- Quantum Computational Complexity (2008, background): “Interactive proof systems, or interactive proofs for short, were first introduced by Babai [17, 20] and Goldwasser, Micali, and Rackoff [55, 56], and have led to remarkable discoveries in complexity such as the PCP Theorem [15, 16, 43].”