Interactive and probabilistic proof-checking
From MaRDI portal
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)
Recommendations
Cites work
- scientific article; zbMATH DE number 5595151 (Why is no real title available?)
- scientific article; zbMATH DE number 5081837 (Why is no real title available?)
- scientific article; zbMATH DE number 1241395 (Why is no real title available?)
- scientific article; zbMATH DE number 1256785 (Why is no real title available?)
- scientific article; zbMATH DE number 1559516 (Why is no real title available?)
- scientific article; zbMATH DE number 1559563 (Why is no real title available?)
- scientific article; zbMATH DE number 1559564 (Why is no real title available?)
- scientific article; zbMATH DE number 1775382 (Why is no real title available?)
- scientific article; zbMATH DE number 1775406 (Why is no real title available?)
- scientific article; zbMATH DE number 1775415 (Why is no real title available?)
- scientific article; zbMATH DE number 1775419 (Why is no real title available?)
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- scientific article; zbMATH DE number 861531 (Why is no real title available?)
- scientific article; zbMATH DE number 4185024 (Why is no real title available?)
- Algebraic methods for interactive proof systems
- Approximation algorithms for NP-hard problems.
- Approximation algorithms for combinatorial problems
- Are there interactive protocols for co-NP languages?
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Does co-NP have short interactive proofs ?
- Efficient probabilistically checkable proofs and applications to approximations
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Games against nature
- Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
- Improved non-approximability results
- Modern cryptography, probabilistic proofs and pseudo-randomness
- Non-deterministic exponential time has two-prover interactive protocols
- On the power of multi-prover interactive protocols
- Optimization, approximation, and complexity classes
- Probabilistic checking of proofs
- Proof verification and the hardness of approximation problems
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- Statistical zero-knowledge languages can be recognized in two rounds
- The Knowledge Complexity of Interactive Proof Systems
- The random oracle hypothesis is false
- Two prover protocols, low error at affordable rates
Cited in
(11)- Interactive observability in Ludics: the geometry of tests
- Interactive Coding for Interactive Proofs
- Corrigendum to: ``Efficient probabilistic checkable proofs and applications to approximation
- scientific article; zbMATH DE number 4080913 (Why is no real title available?)
- scientific article; zbMATH DE number 1629956 (Why is no real title available?)
- scientific article; zbMATH DE number 727431 (Why is no real title available?)
- Authoring Verified Documents by Interactive Proof Construction and Verification in Text-Editors
- Probabilistic Proof Systems: A Primer
- scientific article; zbMATH DE number 1789920 (Why is no real title available?)
- scientific article; zbMATH DE number 412256 (Why is no real title available?)
- An Interactive Driver for Goal-directed Proof Strategies
This page was built for publication: Interactive and probabilistic proof-checking
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1577488)
