Probabilistic Proof Systems: A Primer

DOI10.1561/0400000023zbMATH Open1195.68048OpenAlexW4206014747MaRDI QIDQ3530806FDOQ3530806

Authors: Oded Goldreich 

Publication date: 20 October 2008

Published in: Foundations and Trends® in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1561/0400000023

Recommendations

• Probabilistic proof systems -- a survey
• scientific article; zbMATH DE number 850075
• Probabilistic verification of proofs
• scientific article; zbMATH DE number 1072531
• Interactive and probabilistic proof-checking

zbMATH Keywords

randomizationcomplexity classeszero-knowledge proofsproof systemsprobabilistically checkable proofsinteractive proofs

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Cited In (3)

• Challenging epistemology: Interactive proofs and zero knowledge
• Probabilistic proof systems -- a survey
• Towards a structural proof theory of probabilistic \(\mu\)-calculi

This page was built for publication: Probabilistic Proof Systems: A Primer

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