Interactive and probabilistic proof-checking
From MaRDI portal
Publication:1577488
DOI10.1016/S0168-0072(00)00017-8zbMath0959.68043OpenAlexW1996183456MaRDI QIDQ1577488
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
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Non-deterministic exponential time has two-prover interactive protocols
- Statistical zero-knowledge languages can be recognized in two rounds
- Games against nature
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Does co-NP have short interactive proofs ?
- Are there interactive protocols for co-NP languages?
- Optimization, approximation, and complexity classes
- Approximation algorithms for combinatorial problems
- Modern cryptography, probabilistic proofs and pseudo-randomness
- The random oracle hypothesis is false
- On the power of multi-prover interactive protocols
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Two prover protocols
- Improved non-approximability results
- Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
- Proof verification and the hardness of approximation problems
- The Knowledge Complexity of Interactive Proof Systems
- Probabilistic checking of proofs
- Algebraic methods for interactive proof systems
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Efficient probabilistically checkable proofs and applications to approximations
This page was built for publication: Interactive and probabilistic proof-checking
