On Yao's XOR-Lemma

Webpage for a paper by Oded Goldreich, Noam Nisan, and Avi Wigderson


Abstract

A fundamental lemma of Yao states that computational weak-unpredictability of Boolean predicates is amplified when 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 original 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 (1989) and some elementary observation, we derive the XOR-Lemma.

Comment regarding the 2010 revision

An early version of this survey appeared as TR95-050 of {\em ECCC}, and was revised several times (with the latest revision posted in January 1999). 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.

Material available on-line


Back to either Oded Goldreich's homepage. or general list of papers.