Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR95-056 | 26th November 1995 00:00

Three XOR-Lemmas -- An Exposition


Authors: Oded Goldreich
Publication: 27th November 1995 10:47
Downloads: 1312


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 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 most notable XOR Lemma~-- that is the so-called Yao XOR Lemma
is not discussed here.

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 author, and are mainly due to several

ISSN 1433-8092 | Imprint