Probabilistic verification of proofs

zbMATH Open0912.68190MaRDI QIDQ1126840FDOQ1126840

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

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

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

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)

Cited In (11)

• Probabilistic verification of Boolean functions
• On memoryless provers and insincere verifiers
• Fast approximate probabilistically checkable proofs
• Title not available (Why is that?)
• Probabilistic verification and approximation
• Title not available (Why is that?)
• 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)