Interactive and probabilistic proof-checking
DOI10.1016/S0168-0072(00)00017-8zbMATH Open0959.68043OpenAlexW1996183456MaRDI QIDQ1577488FDOQ1577488
Authors: Luca Trevisan 
Publication date: 4 September 2000
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0168-0072(00)00017-8
Recommendations
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)
Cites Work
- Approximation algorithms for combinatorial problems
- Optimization, approximation, and complexity classes
- Approximation algorithms for NP-hard problems.
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Proof verification and the hardness of approximation problems
- Probabilistic checking of proofs
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Non-deterministic exponential time has two-prover interactive protocols
- Title not available (Why is that?)
- Improved non-approximability results
- Title not available (Why is that?)
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Does co-NP have short interactive proofs ?
- The Knowledge Complexity of Interactive Proof Systems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Statistical zero-knowledge languages can be recognized in two rounds
- Title not available (Why is that?)
- Efficient probabilistically checkable proofs and applications to approximations
- Title not available (Why is that?)
- Algebraic methods for interactive proof systems
- On the power of multi-prover interactive protocols
- Games against nature
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Title not available (Why is that?)
- Title not available (Why is that?)
- Modern cryptography, probabilistic proofs and pseudo-randomness
- Title not available (Why is that?)
- Are there interactive protocols for co-NP languages?
- The random oracle hypothesis is false
- Title not available (Why is that?)
- Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
- Two prover protocols, low error at affordable rates
- Title not available (Why is that?)
Cited In (11)
- Interactive Coding for Interactive Proofs
- Interactive observability in Ludics: the geometry of tests
- Title not available (Why is that?)
- Corrigendum to: ``Efficient probabilistic checkable proofs and applications to approximation
- Title not available (Why is that?)
- Authoring Verified Documents by Interactive Proof Construction and Verification in Text-Editors
- Title not available (Why is that?)
- Probabilistic Proof Systems: A Primer
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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)
