Probabilistic proof systems — A survey
From MaRDI portal
Publication:5048957
DOI10.1007/BFb0023492zbMath1498.68112MaRDI QIDQ5048957
Publication date: 9 November 2022
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Cryptography (94A60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Non-deterministic exponential time has two-prover interactive protocols
- Bit commitment using pseudorandomness
- Probabilistic encryption
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Minimum disclosure proofs of knowledge
- Self-testing/correcting with applications to numerical problems
- Definitions and properties of zero-knowledge proof systems
- The Knowledge Complexity of Interactive Proof Systems
- The Complexity of Decision Versus Search
- Algebraic methods for interactive proof systems
- IP = PSPACE
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- Robust Characterizations of Polynomials with Applications to Program Testing
- On the hardness of approximating minimization problems
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Probabilistic proof systems — A survey