On the concrete efficiency of probabilistically-checkable proofs
By Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer. 2013
80 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
- Eli Ben-Sasson
- Srinath T. V. Setty
- Michael Riabzev
- Iddo Bentov
- Eran Tromer
- Justin Thaler
- Alessandro Chiesa
- Madars Virza
In Computational Theory and Mathematics
- Eli Ben-Sasson
- Srinath T. V. Setty
- Michael Riabzev
- Iddo Bentov
- Yinon Horesh
- Madars Virza
- Alessandro Chiesa
- Justin Thaler
Citations in the corpus
- Scalable Zero Knowledge with No Trusted Setup (2019, methodology): “the second work [17] bounds the prover running time and also proves the proof of knowledge”
- Ligero: Lightweight Sublinear Arguments Without a Trusted Setup (2017, methodology): “In particular, one could consider constructions of PCPs based on bivariate polynomials such as the one of Polishchuk and Spielman [40] (see [8] for work in this direction), or the zero-knowledge”
- Computational Integrity with a Public Random String from Quasi-Linear PCPs (2017, methodology): “To verify the integrity of random access memory instructions (such as load and store) we follow [13, 14] and use a pair of execution traces.”
- Practical verified computation with streaming interactive proofs (2011, background): “[13, 14] focuses on the development of short PCPs that might be suitable for use in practice – such PCPs can be combined with standard cryptographic tools to yield interactive arguments.”
- 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.”
- Scalable, transparent, and post-quantum secure computational integrity (2018, methodology): “It follows the approach of [19, 20] and uses a pair of AIR constraints — one for verifying the validity of consecutive time steps and another for verifying memory consistency; the latter set of constraints is applied to a permutation of the steps of the execution trace, and part of the witness is a ”
- 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].”