Probabilistic Proof Systems: A Primer

DOI10.1561/0400000023MaRDI QIDQ3530806zbMATH OpenOpenAlexFDO

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

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)

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

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)