Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > KNOWLEDGE COMPLEXITY:
Reports tagged with Knowledge Complexity:
TR94-007 | 12th December 1994
Oded Goldreich, Rafail Ostrovsky, Erez Petrank

#### Computational Complexity and Knowledge Complexity

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 ${\cal BPP}^{\cal NP}$. Prior
to this work, for languages with greater-than-zero knowledge
complexity (and specifically, even for knowledge complexity 1) only
trivial computational complexity bounds ... more >>>

TR00-084 | 6th November 2000

#### A Complete Problem for Statistical Zero Knowledge

We present the first complete problem for SZK, the class of (promise)
problems possessing statistical zero-knowledge proofs (against an
honest verifier). The problem, called STATISTICAL DIFFERENCE, is to
decide whether two efficiently samplable distributions are either
statistically close or far apart. This gives a new characterization
of SZK that makes ... more >>>

ISSN 1433-8092 | Imprint