Rafail Ostrovsky - Publications

Computational Complexity and Knowledge Complexity.

Oded Goldreich, Rafail Ostrovsky, Erez Petrank


We study the computational complexity of languages which have interactive proofs of logarithmic knowledge complexity. We show that all such languages can be recognized in BPP}NP. Prior to this work for languages with grater -than-zero knowledge complexity(and specifically, even for knowledge complexity 1) only trivial computational complexity bounds (i.e.,only recognizability in PSP ACE=IPwere known. In the course of our proof, we relate statistical Knowledge-complexity with perfect knowledge-complexity;specifically, we show that for the honest verifier, these hi-erachies coinside up to a logarithmic additive term (i.e., SKC(k(.))PKC(k(.))).

comment: Preliminary version appeared in the Twenty-sixth ACM Symposium on Theory of Computing (STOC-94) Full version in SIAM Journal on Computing, 27(4):1116-1141, August 1998.

Fetch PostScript file of the paper     Fetch PDF file of the paper

Back to Publications List