ECCC-Report TR95-056https://eccc.weizmann.ac.il/report/1995/056Comments and Revisions published for TR95-056en-usMon, 27 Nov 1995 10:47:46 +0200
Paper TR95-056
| Three XOR-Lemmas -- An Exposition |
Oded Goldreich
https://eccc.weizmann.ac.il/report/1995/056We 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
Mon, 27 Nov 1995 10:47:46 +0200https://eccc.weizmann.ac.il/report/1995/056