Computational complexity and knowledge complexity (extended abstract)

DOI10.1145/195058.195406zbMath1345.68173OpenAlexW1984996906MaRDI QIDQ2817645

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

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

Related Items

Practical proofs of knowledge without relying on theoretical proofs of membership on languages, On relationships between statistical zero-knowledge proofs, A language-dependent cryptographic primitive, Uniform generation of NP-witnesses using an NP-oracle