Rafail Ostrovsky - Publications


Computational Complexity and Knowledge Complexity.

Oded Goldreich, Rafail Ostrovsky, Erez Petrank

Abstract:

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