Probabilistic proof systems -- a survey

DOI10.1007/BFB0023492MaRDI QIDQ5048957zbMATH OpenFDO

Authors Oded Goldreich

Publication date 9 November 2022

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

Full work available at URL https://doi.org/10.1007/BFB0023492

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60)

Recommendations

• scientific article; zbMATH DE number 850075
• Probabilistic Proof Systems: A Primer
• scientific article; zbMATH DE number 4087662
• Probabilistic verification of proofs
• scientific article; zbMATH DE number 4106274

Cites work

• Algebraic methods for interactive proof systems
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Bit commitment using pseudorandomness
• Definitions and properties of zero-knowledge proof systems
• scientific article; zbMATH DE number 4213418 (Why is no real title available?)
• scientific article; zbMATH DE number 1256748 (Why is no real title available?)
• scientific article; zbMATH DE number 1256635 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• scientific article; zbMATH DE number 1263223 (Why is no real title available?)
• scientific article; zbMATH DE number 1306875 (Why is no real title available?)
• scientific article; zbMATH DE number 708807 (Why is no real title available?)
• scientific article; zbMATH DE number 708820 (Why is no real title available?)
• scientific article; zbMATH DE number 4185024 (Why is no real title available?)
• IP = PSPACE
• Minimum disclosure proofs of knowledge
• Non-deterministic exponential time has two-prover interactive protocols
• On the hardness of approximating minimization problems
• Probabilistic encryption
• 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
• Self-testing/correcting with applications to numerical problems
• The Complexity of Decision Versus Search
• The Knowledge Complexity of Interactive Proof Systems

Cited in

(7)

• Probabilistic verification of proofs
• Interactive and probabilistic proof-checking
• Towards a structural proof theory of probabilistic \(\mu\)-calculi
• Probabilistic Proof Systems: A Primer
• scientific article; zbMATH DE number 4087662 (Why is no real title available?)
• scientific article; zbMATH DE number 1072531 (Why is no real title available?)
• scientific article; zbMATH DE number 850075 (Why is no real title available?)

This page was built for publication: Probabilistic proof systems -- a survey

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5048957)