Probabilistic verification of proofs

MaRDI 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

computational complexitycombinatorial optimization

Mathematics Subject Classification ID

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

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

(11)

• Probabilistic verification of Boolean functions
• On memoryless provers and insincere verifiers
• Fast approximate probabilistically checkable proofs
• scientific article; zbMATH DE number 2086517 (Why is no real title available?)
• Probabilistic verification and approximation
• scientific article; zbMATH DE number 727431 (Why is no real title available?)
• Probabilistic Proof Systems: A Primer
• Checking identities is computationally intractable NP-hard and therefore human provers will always be needed
• Probabilistic proof systems -- a survey
• On the concrete efficiency of probabilistically-checkable proofs
• Computationally Sound Proofs

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)