Probabilistic proof systems — A survey

DOI10.1007/BFb0023492zbMath1498.68112MaRDI QIDQ5048957

Oded Goldreich

Publication date: 9 November 2022

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

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