Yao's XOR Lemma

Yao's XOR Lemma is a hardness amplification result in computational complexity theory that strengthens the Direct Product Theorem. It states that if a function f is mildly hard to compute, then the XOR of f evaluated on k independent inputs — f(x_1) ⊕ ... ⊕ f(x_k) — is extremely hard to predict. The XOR structure is more resilient than the direct product because partial information about individual outputs does not reveal the XOR. Introduced by Andrew Yao, the lemma is a cornerstone of the derandomization program, connecting hardness amplification to pseudorandom generators. The lemma exemplifies a broader systems principle: combining weakly reliable components through parity operations can produce strongly reliable aggregates — a pattern visible in error-correcting codes and neural ensemble coding.

See also: Direct Product Theorem, Hardness Amplification, Derandomization, Error-Correcting Codes