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

complexity classesinteractive proofsprobabilistically checkable proofsproof systemsrandomizationzero-knowledge proofs

Mathematics Subject Classification ID

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

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

(5)

• Probabilistic verification of proofs
• Towards a structural proof theory of probabilistic \(\mu\)-calculi
• scientific article; zbMATH DE number 850075 (Why is no real title available?)
• Probabilistic proof systems -- a survey
• Challenging epistemology: Interactive proofs and zero knowledge

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)