Probabilistic verification of proofs

DOI10.4171/DMS/1-3/45MaRDI QIDQ1126840zbMATH OpenFDO

Authors Madhu Sudan

Publication date 5 August 1998

Published in Documenta Mathematica (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/224168, http://www.emis.de/journals/DMJDMV/xvol-icm/14/Sudan.MAN.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

combinatorial optimizationcomputational complexity

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

This is a survey of probabilistic proof verification as proposed by \textit{S. Goldwasser}, \textit{S. Micali} and \textit{C. Rackoff} [SIAM J. Comput. 18, No. 1, 186-208 (1989; Zbl 0677.68062)] including descriptions of some of the methods used in the construction of probabilistically checkable proofs.

Recommendations

• Probabilistic proof systems -- a survey
• scientific article; zbMATH DE number 850075
• Probabilistic Proof Systems: A Primer
• Interactive and probabilistic proof-checking
• On Dinur’s proof of the PCP theorem

Cited in

(16)

• Fast approximate probabilistically checkable proofs
• Probabilistic verification of proofs in calculuses
• Probabilistic verification and approximation
• Checking identities is computationally intractable NP-hard and therefore human provers will always be needed
• scientific article; zbMATH DE number 4205986 (Why is no real title available?)
• Probabilistic Proof Systems: A Primer
• On memoryless provers and insincere verifiers
• scientific article; zbMATH DE number 512858 (Why is no real title available?)
• scientific article; zbMATH DE number 727431 (Why is no real title available?)
• \((\text{poly}(\log\log n),\text{poly}(\log\log n))\)-restricted verifiers are unlikely to exist for languages in \({\mathcal NP}\)
• Computationally Sound Proofs
• scientific article; zbMATH DE number 2086517 (Why is no real title available?)
• scientific article; zbMATH DE number 850075 (Why is no real title available?)
• Probabilistic proof systems -- a survey
• On the concrete efficiency of probabilistically-checkable proofs
• Probabilistic verification of Boolean functions

This page was built for publication: Probabilistic verification of proofs

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