Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR95-050 | 3rd July 2010 09:09

On Yao's XOR-Lemma

RSS-Feed




Revision #2
Authors: Oded Goldreich, Noam Nisan, Avi Wigderson
Accepted on: 3rd July 2010 09:09
Downloads: 4274
Keywords: 


Abstract:



Changes to previous version:

Since the first publication of this survey, Yao's XOR Lemma has been the subject of intensive research. The current revision contains a short review of this research (see Section 7), but the main text (i.e., Sections 1-6) is not updated according to these subsequent discoveries. The current version also include a new appendix (Appendix B), which discusses a variant of the XOR Lemma, called the Selective XOR Lemma.


Revision #1 to TR95-050 | 14th January 1999 00:00

On Yao's XOR-Lemma. Revision of: TR95-050





Revision #1
Authors: Oded Goldreich, Noam Nisan, Avi Wigderson
Accepted on: 14th January 1999 00:00
Downloads: 3710
Keywords: 


Abstract:

A fundamental Lemma of Yao states that computational
weak-unpredictability
of functions gets amplified if the results of several independent
instances are XOR together.
We survey two known proofs of Yao's Lemma and present
a third alternative proof.
The third proof proceeds by first proving that a function constructed
by {\em concatenating} the values of the function
on several independent instances is much more unpredictable,
with respect to specified complexity bounds,
than the original function.
This statement turns out to be easier to prove than the XOR-Lemma.
Using a result of Goldreich and Levin
and some elementary observation, we derive the XOR-Lemma.


Paper:

TR95-050 | 15th October 1995 00:00

On Yao's XOR-Lemma





TR95-050
Authors: Oded Goldreich, Noam Nisan, Avi Wigderson
Publication: 20th October 1995 08:17
Downloads: 2315
Keywords: 


Abstract:


Comment(s):

Comment #1 to TR95-050 | 8th December 1995 09:03

Errata to our report "On Yao's XOR-Lemma" Comment on: TR95-050





Comment #1
Authors: Oded Goldreich, Noam Nisan, Avi Wigderson
Accepted on: 8th December 1995 09:03
Downloads: 2534
Keywords: 


Abstract:

We correct some typos in the proof of Lemma 12.
Specifically, the probability bound in Claim 12.3
should be $(1/2)+2\epsilon$ (rather than $(1/2)+(\epsilon/2)$)
and the last line in the bound on the expectation
of $\sum_{x\in C}\zeta_xw_x$
should be $\rho(n)\cdot[(1/2)+\epsilon]$
(rather than $\rho(n)\cdot[(1/2)-\epsilon]$).




ISSN 1433-8092 | Imprint