Oded Goldreich

We provide an exposition of three Lemmas which relate

general properties of distributions

with the exclusive-or of certain bit locations.

The first XOR-Lemma, commonly attributed to U.V. Vazirani,

relates the statistical distance of a distribution from uniform

to the maximum bias of the xor of certain bit positions.

more >>>

Oded Goldreich, Bernd Meyer

We present a simple proof to the existence of a probability ensemble

with tiny support which cannot be distinguished from the uniform ensemble

by any recursive computation.

Since the support is tiny (i.e, sub-polynomial),

this ensemble can be distinguish from the uniform ensemble

by a (non-uniform) family ...
more >>>

Oded Goldreich, Madhu Sudan

We consider the existence of pairs of probability ensembles which

may be efficiently distinguished given $k$ samples

but cannot be efficiently distinguished given $k'<k$ samples.

It is well known that in any such pair of ensembles it cannot be that

both are efficiently computable

(and that such phenomena ...
more >>>

Zvika Brakerski, Oded Goldreich

We study methods of converting algorithms that distinguish pairs

of distributions with a gap that has an absolute value that is noticeable

into corresponding algorithms in which the gap is always positive.

Our focus is on designing algorithms that, in addition to the tested string,

obtain a ...
more >>>

Nathan Geier

Assume that $X_0,X_1$ (respectively $Y_0,Y_1$) are $d_X$ (respectively $d_Y$) indistinguishable for circuits of a given size. It is well known that the product distributions $X_0Y_0,\,X_1Y_1$ are $d_X+d_Y$ indistinguishable for slightly smaller circuits. However, in probability theory where unbounded adversaries are considered through statistical distance, it is folklore knowledge that in ... more >>>