Randomness in interactive proofs
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 563-572vol.2
- https://doi.org/10.1109/fscs.1990.89577
Abstract
The quantitative aspects of randomness in interactive proof systems are studied. The result is a randomness-efficient error-reduction technique: given an Arthur-Merlin proof system (error probabilityKeywords
This publication has 20 references indexed in Scilit:
- On the power of two-point based samplingJournal of Complexity, 1989
- The Knowledge Complexity of Interactive Proof SystemsSIAM Journal on Computing, 1989
- Dispersers, deterministic amplification, and weak random sourcesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- How to recycle random bitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Does co-NP have short interactive proofs?Information Processing Letters, 1987
- Eigenvalues and expandersCombinatorica, 1986
- Private coins versus public coins in interactive proof systemsPublished by Association for Computing Machinery (ACM) ,1986
- How to Generate Cryptographically Strong Sequences of Pseudorandom BitsSIAM Journal on Computing, 1984
- Explicit constructions of linear-sized superconcentratorsJournal of Computer and System Sciences, 1981
- Universal classes of hash functionsJournal of Computer and System Sciences, 1979