Class Description

AVBPP: Average-Case BPP

Defined in [OW93] to be the class of decision problems that have a good average-case BPP algorithm, whenever the input is chosen from an efficiently samplable distribution.

Note that this is not the same as the BPP version of AvgP.

Linked From

CZK: Computational Zero-Knowledge

Same as SZK, except that now the two distributions are merely required to be computationally indistinguishable by any BPP algorithm; they don't have to be statistically close. (The "two distributions" are (1) the distribution over the verifier's view of their interaction with the prover, conditioned on the verifier's random coins, and (2) the distribution over views that the verifier can simulate without the prover's help.)

Unlike SZK, it is not known if CZK is closed under complement. CZK is now known to share other properties with SZK: the verifier may as well be honest and may as well show their coins, and CZK is closed under unions [Vad06]. (Previously, these properties were only established in the presence of one-way functions [GMW91].)

Assuming the existence of one-way functions, CZK contains NP [GMW91], and actually equals IP=PSPACE [BGG+90]. However, none of these implications of one-way functions relativize (Impagliazzo, unpublished).

On the other hand, if one-way functions do not exist then CZK = AVBPP [OW93].

Contains PZK and SZK.

More about...