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.

Abstract:

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

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

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]$).