On the Complexity of Interactive Proofs with Bounded Communication
By Oded Goldreich, J. Håstad. 1998
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- Dan Boneh
- Benedikt Bünz
- Jens Groth
- Eli Ben-Sasson
- Srinath T. V. Setty
- Jonathan Bootle
- Brent Waters
- Ran Canetti
Citations in the corpus
- Bulletproofs: Short Proofs for Confidential Transactions and More (2018, background): “The works [GH98,GVW02] show that in general, interactive proofs cannot have communication costs smaller than the witness size, unless some very surprising results in complexity theory hold.”
- Efficient Arguments without Short PCPs (2007, unknown): “Before describing our approach, we give some background to put it in context.”
- Recursive composition and bootstrapping for SNARKS and proof-carrying data (2013, background): “Recursive Composition and Bootstrapping for SNARKs and Proof-Carrying Data Nir Bitansky* Ran Canetti Alessandro Chiesa Eran Tromer nirbitan@tau.ac.il canetti@tau.ac.il alexch@csail.mit.edu tromer@tau.ac.il Tel Aviv University Boston University and MIT Tel Aviv University Tel Aviv University ABSTR”
- Fast reductions from RAMs to delegatable succinct constraint satisfaction problems: extended abstract (2013, background): “Such proof systems cannot be statistically sound (under plausible complexity-theoretic assumptions [18, 42, 45, 92]) so that one must settle for argument”
- Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation (2016, background): “ewhat different from ours (which is univariate). Gur and Rothblum [GR15] obtain a similar square-root speedup for checking sums in the “non-interactive property testing” setting. Goldreich and Hastad [GH98] and Goldreich, Vadhan, and Wigderson [GVW02] studied interactive proofs which seek to minimiz”
- Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting (2016, background): “However, proofs cannot in general have communication that is smaller than the witness size unless surprising results about the complexity of solving SAT instances hold [15, 17].”