Technical Report CS0681

Authors: O Goldreich
PDF - RevisedCS0681.revised.pdf
Abstract: In this note we provide an exposition of three Lemmi 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 and the maximum bias of the xor of certain bit positions. The second XOR-Lemma, due to U.V. Vazirani and V.V. Vazirani, is a computational analogue of the first. It relates the pseudorandomness of a distribution with the difficulty of predicting the xor of bits in particular or random positions. The third Lemma, due to Goldreich and Levin, relates the difficulty of retrieving a string and the unpredictability of the xor of random bit positions. The proofs presented here differ from the proofs presented in the original works. Furthermore, these proofs are believed to be simpler, of wider applicability and yield somewhat better results. Credits for these improved proofs and their presentation are only partially due to the author, and are mainly due to several other researchers.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1991
To the main CS technical reports page

Computer science department, Technion