Computational complexity and knowledge complexity (extended abstract)

DOI10.1145/195058.195406zbMATH Open1345.68173OpenAlexW1984996906MaRDI QIDQ2817645FDOQ2817645

Authors: Oded Goldreich, Rafail Ostrovsky, Erez Petrank 

Publication date: 1 September 2016

Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/195058.195406

Recommendations

• Computational Complexity and Knowledge Complexity
• On the knowledge complexity of \(\mathcal N\mathcal P\)
• On relationships between statistical zero-knowledge proofs
• Statistical zero-knowledge languages can be recognized in two rounds
• The knowledge complexity of interactive proof-systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of proofs (03F20)

Cited In (6)

• On relationships between statistical zero-knowledge proofs
• Practical proofs of knowledge without relying on theoretical proofs of membership on languages
• The complexity of reasoning about knowledge and time. I: Lower bounds
• Uniform generation of NP-witnesses using an NP-oracle
• A language-dependent cryptographic primitive
• On the knowledge complexity of \(\mathcal N\mathcal P\)

This page was built for publication: Computational complexity and knowledge complexity (extended abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2817645)