Computational complexity and knowledge complexity (extended abstract)

DOI10.1145/195058.195406MaRDI QIDQ2817645zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(9)

• The complexity of reasoning about knowledge and time. I: Lower bounds
• Quantifying knowledge complexity
• Practical proofs of knowledge without relying on theoretical proofs of membership on languages
• On the knowledge complexity of \(\mathcal N\mathcal P\)
• Uniform generation of NP-witnesses using an NP-oracle
• On relationships between statistical zero-knowledge proofs
• Computational Complexity and Knowledge Complexity
• scientific article; zbMATH DE number 1263223 (Why is no real title available?)
• A language-dependent cryptographic primitive

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)