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. The second ... more >>>

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 of small circuits. ... more >>>

We consider the existence of pairs of probability ensembles which may be efficiently distinguished given $k$ samples but cannot be efficiently distinguished given $k'more >>>

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 fixed number of ... more >>>